結果

問題 No.241 出席番号(1)
ユーザー threepipes_s
提出日時 2015-07-10 23:01:04
言語 Java8
(openjdk 1.8.0.222)
結果
AC  
実行時間 107 ms
コード長 4,349 Byte
コンパイル時間 1,791 ms
使用メモリ 33,988 KB
最終ジャッジ日時 2019-10-13 05:48:21

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_system_test1.txt AC 79 ms
30,708 KB
99_system_test2.txt AC 87 ms
28,980 KB
99_system_test3.txt AC 86 ms
31,824 KB
99_system_test4.txt AC 80 ms
30,388 KB
99_system_test5.txt AC 97 ms
31,072 KB
99_system_test6.txt AC 76 ms
32,196 KB
99_system_test7.txt AC 101 ms
32,056 KB
99_system_test8.txt AC 80 ms
30,712 KB
challenge01.txt AC 80 ms
30,580 KB
challenge02.txt AC 81 ms
32,116 KB
sample1.txt AC 77 ms
29,504 KB
sample2.txt AC 77 ms
32,140 KB
sample3.txt AC 82 ms
31,604 KB
system_test1.txt AC 83 ms
32,860 KB
system_test2.txt AC 105 ms
31,292 KB
system_test3.txt AC 103 ms
33,988 KB
test1.txt AC 75 ms
31,264 KB
test2.txt AC 76 ms
32,208 KB
test3.txt AC 76 ms
31,336 KB
test4.txt AC 77 ms
31,276 KB
test5.txt AC 76 ms
30,792 KB
test6.txt AC 74 ms
30,588 KB
test7.txt AC 75 ms
29,444 KB
test8.txt AC 89 ms
30,144 KB
test9.txt AC 106 ms
32,176 KB
test10.txt AC 106 ms
30,472 KB
test11.txt AC 106 ms
30,092 KB
test12.txt AC 106 ms
31,492 KB
test13.txt AC 107 ms
31,400 KB
test14.txt AC 105 ms
30,376 KB
test15.txt AC 100 ms
31,992 KB
test16.txt AC 105 ms
31,884 KB
テストケース一括ダウンロード

ソースコード

diff #
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Comparator;
import java.util.HashSet;

public class Main {
	static HashSet<String> set = new HashSet<String>();
	public static void main(String[] args) throws NumberFormatException,
	IOException {
		Solve solve = new Solve();
		solve.solve();
	}
}
class Solve{
	ContestScanner in;
	Solve() throws FileNotFoundException{
		in = new ContestScanner();
	}
	
	final static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
	final static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
	int s, t;
	int[][] cap;
	void solve() throws IOException{
		int n = in.nextInt();
		Node[] node = new Node[n*2+2];
		int size = n*2+2;
		for(int i=0; i<size; i++){
			node[i] = new Node(i);
		}
		cap = new int[size][size];
		for(int i=0; i<n; i++){
			node[n*2].createEdge(node[i]);
			node[i].createEdge(node[n*2]);
			cap[n*2][i] = 1;
		}
		s = n*2;
		t = n*2+1;
		for(int i=n; i<n*2; i++){
			node[t].createEdge(node[i]);
			node[i].createEdge(node[t]);
			cap[i][t] = 1;
		}
		for(int i=0; i<n; i++){
			int a = in.nextInt();
			for(int j=n; j<n*2; j++){
				int id = j-n;
				if(id == a) continue;
				node[i].createEdge(node[j]);
				node[j].createEdge(node[i]);
				cap[i][j] = 1;
			}
		}
		used = new BitSet(size);
		int res = 0;
		while(true){
			used.clear();
			int flow = flow(node[s], 1);
			if(flow == 0) break;
			res += flow;
		}
		if(res != n){
			System.out.println(-1);
			return;
		}
		for(int i=0; i<n; i++){
			for(int j=n; j<n*2; j++){
				if(cap[j][i] == 1){
					System.out.println(j-n);
					break;
				}
			}
		}
	}
	
	BitSet used;
	int flow(Node from, int flow){
		if(from.id == t) return flow;
		if(used.get(from.id)) return 0;
		used.set(from.id);
		for(Node v: from.edge){
			if(cap[from.id][v.id] == 0) continue;
			int f = flow(v, Math.min(flow, cap[from.id][v.id]));
			if(f == 0) continue;
			cap[from.id][v.id] -= f;
			cap[v.id][from.id] += f;
			return f;
		}
		return 0;
	}
}

class Timer{
	long time;
	public void set(){
		time = System.currentTimeMillis();
	}
	
	public long stop(){
		return System.currentTimeMillis()-time;
	}
}

class Node{
	int id;
	ArrayList<Node> edge = new ArrayList<Node>();
	public Node(int id) {
		this.id = id;
	}
	public void createEdge(Node node) {
		edge.add(node);
	}
}

class MyComp implements Comparator<int[]> {
	final int idx;
	public MyComp(int idx){
		this.idx = idx;
	}
	public int compare(int[] a, int[] b) {
		return a[idx] - b[idx];
	}
}

class Reverse implements Comparator<Integer> {
	public int compare(Integer arg0, Integer arg1) {
		return arg1 - arg0;
	}
}


class ContestWriter {
	private PrintWriter out;

	public ContestWriter(String filename) throws IOException {
		out = new PrintWriter(new BufferedWriter(new FileWriter(filename)));
	}

	public ContestWriter() throws IOException {
		out = new PrintWriter(System.out);
	}

	public void println(String str) {
		out.println(str);
	}
	
	public void println(Object obj) {
		out.println(obj);
	}

	public void print(String str) {
		out.print(str);
	}
	
	public void print(Object obj) {
		out.print(obj);
	}

	public void close() {
		out.close();
	}
}

class ContestScanner {
	private BufferedReader reader;
	private String[] line;
	private int idx;

	public ContestScanner() throws FileNotFoundException {
		reader = new BufferedReader(new InputStreamReader(System.in));
	}

	public ContestScanner(String filename) throws FileNotFoundException {
		reader = new BufferedReader(new InputStreamReader(new FileInputStream(
				filename)));
	}

	public String nextToken() throws IOException {
		if (line == null || line.length <= idx) {
			line = reader.readLine().trim().split(" ");
			idx = 0;
		}
		return line[idx++];
	}
	
	public String readLine() throws IOException{
		return reader.readLine();
	}

	public long nextLong() throws IOException, NumberFormatException {
		return Long.parseLong(nextToken());
	}

	public int nextInt() throws NumberFormatException, IOException {
		return (int) nextLong();
	}

	public double nextDouble() throws NumberFormatException, IOException {
		return Double.parseDouble(nextToken());
	}
}
0