Codeforces #397 Div1+Div2 D Artsem and Saunders

問題

codeforces.com

考察

多分これは,与えられた2つの式

• 

• 

から、式を変形して考察を進めれば良いのかな？

@tookunn_1213 この単射ではないっていうのはh(a) = h(b)の場合,h(a) = h(b) = Aとして、g(h(a)) = a,g(h(b)) = bで,g(A) = a,bはaかbどちらかに一意に定まっていないということか

— tookunn (@tookunn_1213) 2017年2月16日

@tookunn_1213 h(g(x))とh(g(y))は同一の値になることが分かって、g(h(g(x))) = g(h(g(y)))でなきゃいけないからg(x) = g(y)であるということかな（説明が下手）

— tookunn (@tookunn_1213) 2017年2月16日

@tookunn_1213 メモhttps://t.co/phi9xhu1uZ

— tookunn (@tookunn_1213) 2017年2月16日

参考：
pekempey.hatenablog.com

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.NoSuchElementException;

public class D {

	int N;
	int[] g;
	ArrayList<Integer> h;
	HashMap<Integer,Integer> map;


	public void solve() {
		N = nextInt();
		g = new int[N];
		h = new ArrayList<Integer>();
		map = new HashMap<Integer,Integer>();

		for(int i = 0;i < N;i++){

			int f = nextInt()-1;
			/*
			 * fの値ごとにまとめて適当に値を割り当てる
			 * 今回はmap.size()を割り当てる
			 * hには重複なしのfの値を挿入
			 */
			if(!map.containsKey(f)){
				map.put(f, map.size());
				h.add(f);
			}
			
			//fの値をkeyにして適当に割り当てた値をg[i]に
			g[i] = map.get(f);
		}

		for(int i = 0;i < map.size();i++){
			//g(h(x)) = x
			if(g[h.get(i)] != i){
				out.println(-1);
				return;
			}

		}

		out.println(map.size());
		for(int i = 0;i < N;i++){
			if(i != 0)out.print(" ");
			out.print(g[i]+1);
		}
		out.println();
		for(int i = 0;i < map.size();i++){
			if(i != 0)out.print(" ");
			out.print(h.get(i)+1);
		}
		out.println();
	}

	public static void main(String[] args) {
		out.flush();
		new D().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}