Submission #1000589


Source Code Expand

import java.io.*;
import java.util.*;

public class Main {
	FastScanner in;
	PrintWriter out;

	void solve() {
		int n = in.nextInt();
		int xor = 0;
		boolean[] have = new boolean[1 << 20];
		for (int i = 0; i < n; i++) {
			int x = in.nextInt();
			xor ^= x;
			have[x ^ (x - 1)] = true;
		}
		ArrayList<Integer> all = new ArrayList<Integer>();
		for (int i = 0; i < have.length; i++) {
			if (have[i]) {
				all.add(i);
			}
		}
		int res = Integer.MAX_VALUE;
		for (int mask = 0; mask < 1 << all.size(); mask++) {
			int nxor = 0;
			for (int i = 0; i < all.size(); i++) {
				if (((1 << i) & mask) != 0) {
					nxor ^= all.get(i);
				}
			}
			if (nxor == xor) {
				int tmp = Integer.bitCount(mask);
				if (tmp < res) {
					res = tmp;
				}
			}
		}
		out.println(res == Integer.MAX_VALUE ? -1 : res);
	}

	void run() {
		try {
			in = new FastScanner(new File("object.in"));
			out = new PrintWriter(new File("object.out"));

			solve();

			out.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	void runIO() {

		in = new FastScanner(System.in);
		out = new PrintWriter(System.out);

		solve();

		out.close();
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;

		public FastScanner(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public FastScanner(InputStream f) {
			br = new BufferedReader(new InputStreamReader(f));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return null;
				st = new StringTokenizer(s);
			}
			return st.nextToken();
		}

		boolean hasMoreTokens() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

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

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

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

	public static void main(String[] args) {
		new Thread(null, new Runnable() {
			public void run() {
				new Main().runIO();
			}
		}, "1", 1 << 26).start();
	}
}

Submission Info

Submission Time
Task C - Cheating Nim
User qwerty787788
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 2536 Byte
Status WA
Exec Time 238 ms
Memory 24508 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
AC × 8
WA × 18
Set Name Test Cases
Sample example0.txt, example1.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt AC 110 ms 9968 KB
001.txt AC 105 ms 9940 KB
002.txt AC 235 ms 24508 KB
003.txt AC 195 ms 18696 KB
004.txt AC 238 ms 17932 KB
005.txt AC 196 ms 16316 KB
006.txt WA 103 ms 9584 KB
007.txt WA 100 ms 9584 KB
008.txt WA 96 ms 9556 KB
009.txt WA 95 ms 9456 KB
010.txt WA 101 ms 9584 KB
011.txt WA 100 ms 9584 KB
012.txt WA 97 ms 9556 KB
013.txt WA 99 ms 9552 KB
014.txt WA 100 ms 9480 KB
015.txt WA 99 ms 9452 KB
016.txt WA 95 ms 9456 KB
017.txt WA 101 ms 9556 KB
018.txt WA 95 ms 9552 KB
019.txt WA 93 ms 9452 KB
020.txt WA 95 ms 9480 KB
021.txt WA 97 ms 9556 KB
022.txt WA 97 ms 9552 KB
023.txt WA 99 ms 9556 KB
example0.txt AC 120 ms 9968 KB
example1.txt AC 120 ms 9968 KB