Submission #2832111


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int[] A;

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        N = sc.nextInt();
        A = sc.nextIntArray(N);

        System.out.println( solve() );
    }

    static int solve() {
        // xor=0で順番が回ってくると負ける
        // 相手が先手なのでxor=0の状態を作れるかどうかになる
        int xor = 0;
        int eatableBits = 0;
        for (int a : A) {
            xor ^= a;
            eatableBits |= Integer.lowestOneBit(a);
        }
        
        int answer = 0;
        while(xor != 0) {
            int high = Integer.highestOneBit(xor);
            if( (high & eatableBits) != 0 ) {
                xor ^= high;
                xor ^= high-1;
                answer++;

            } else {
                return -1;
            }

        }
        return answer;
    }

    @SuppressWarnings("unused")
    static class FastScanner {

        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

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

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

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

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}

Submission Info

Submission Time
Task C - Cheating Nim
User kusomushi
Language Java8 (OpenJDK 1.8.0)
Score 500
Code Size 2814 Byte
Status AC
Exec Time 182 ms
Memory 36384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 2
AC × 26
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 69 ms 19280 KB
001.txt AC 71 ms 20948 KB
002.txt AC 175 ms 35904 KB
003.txt AC 143 ms 28540 KB
004.txt AC 149 ms 29120 KB
005.txt AC 137 ms 28784 KB
006.txt AC 176 ms 32548 KB
007.txt AC 182 ms 34272 KB
008.txt AC 170 ms 34212 KB
009.txt AC 168 ms 34728 KB
010.txt AC 173 ms 32356 KB
011.txt AC 172 ms 30908 KB
012.txt AC 173 ms 32212 KB
013.txt AC 182 ms 32724 KB
014.txt AC 175 ms 34284 KB
015.txt AC 175 ms 32724 KB
016.txt AC 179 ms 34016 KB
017.txt AC 176 ms 31796 KB
018.txt AC 173 ms 36384 KB
019.txt AC 169 ms 33536 KB
020.txt AC 169 ms 34772 KB
021.txt AC 105 ms 21332 KB
022.txt AC 106 ms 21204 KB
023.txt AC 175 ms 30752 KB
example0.txt AC 67 ms 18388 KB
example1.txt AC 69 ms 18644 KB