Submission #846051


Source Code Expand

Copy
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        static final int MAX_SQRT = (int) 1e5;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] s = new long[n];
            for (int i = 0; i < n; ++i) {
                s[i] = in.nextLong();
            }
            boolean[] pr = new boolean[MAX_SQRT];
            Arrays.fill(pr, 2, pr.length, true);
            int prCount = 0;
            for (int i = 2; i < pr.length; ++i)
                if (pr[i]) {
                    ++prCount;
                    for (int j = i * 2; j < pr.length; j += i) pr[j] = false;
                }
            int[] prs = new int[prCount];
            prCount = 0;
            for (int i = 2; i < pr.length; ++i) if (pr[i]) prs[prCount++] = i;
            int res = 0;
            int cubes = 0;
            long max = 0;
            for (long x : s) max = Math.max(max, x);
            long[] vals = new long[s.length];
            int valsCount = 0;
            outer:
            for (long x : s) {
                long c = 1;
                long o = 1;
                for (int p : prs) {
                    int deg = 0;
                    while (x % p == 0) {
                        ++deg;
                        x /= p;
                    }
                    deg %= 3;
                    if (deg == 1) {
                        c *= p;
                        o *= p;
                        if (o > max) {
                            ++res;
                            continue outer;
                        }
                        o *= p;
                        if (o > max) {
                            ++res;
                            continue outer;
                        }
                    }
                }
                if (x > 1) {
                    ++res;
                    continue;
                }
                if (c == 1) {
                    ++cubes;
                    continue;
                }
                if (c < o) {
                    vals[valsCount++] = c * 2;
                } else {
                    vals[valsCount++] = o * 2 + 1;
                }
            }
            vals = Arrays.copyOf(vals, valsCount);
            Arrays.sort(vals);
            for (int i = 0; i < vals.length; ) {
                int j = i;
                int same = 0;
                while (j < vals.length && vals[j] == vals[i]) {
                    ++same;
                    ++j;
                }
                int diff = 0;
                while (j < vals.length && vals[j] == (vals[i] ^ 1)) {
                    ++diff;
                    ++j;
                }
                res += Math.max(same, diff);
                i = j;
            }
            res += Math.min(1, cubes);
            out.println(res);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

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

    }
}

Submission Info

Submission Time
Task D - Anticube
User Petr
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 4565 Byte
Status WA
Exec Time 5326 ms
Memory 21108 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 3
AC × 10
WA × 4
TLE × 37
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt TLE 5256 ms 20512 KB
02.txt TLE 5256 ms 20400 KB
03.txt TLE 5256 ms 20416 KB
04.txt TLE 5256 ms 20644 KB
05.txt TLE 5256 ms 20376 KB
06.txt TLE 5256 ms 20444 KB
07.txt TLE 5256 ms 20468 KB
08.txt TLE 5256 ms 20032 KB
09.txt TLE 5256 ms 21108 KB
10.txt TLE 5260 ms 20644 KB
11.txt TLE 5256 ms 20328 KB
12.txt TLE 5256 ms 20488 KB
13.txt TLE 5256 ms 20112 KB
14.txt TLE 5256 ms 20208 KB
15.txt TLE 5258 ms 20496 KB
16.txt TLE 5256 ms 20344 KB
17.txt TLE 5256 ms 20456 KB
18.txt TLE 5256 ms 20388 KB
19.txt TLE 5256 ms 20536 KB
20.txt TLE 5256 ms 20776 KB
21.txt TLE 5256 ms 20572 KB
22.txt TLE 5256 ms 20136 KB
23.txt TLE 5326 ms 20372 KB
24.txt TLE 5256 ms 20488 KB
25.txt TLE 5256 ms 20472 KB
26.txt TLE 5256 ms 20416 KB
27.txt WA 4237 ms 20232 KB
28.txt TLE 5256 ms 20100 KB
29.txt TLE 5256 ms 20916 KB
30.txt TLE 5256 ms 20504 KB
31.txt TLE 5256 ms 20436 KB
32.txt TLE 5256 ms 20228 KB
33.txt AC 169 ms 9044 KB
34.txt TLE 5256 ms 20544 KB
35.txt TLE 5256 ms 20464 KB
36.txt AC 164 ms 9044 KB
37.txt TLE 5256 ms 20520 KB
38.txt TLE 5256 ms 20540 KB
39.txt TLE 5256 ms 20448 KB
40.txt TLE 5256 ms 20120 KB
41.txt WA 173 ms 9044 KB
42.txt WA 162 ms 8916 KB
43.txt AC 176 ms 9040 KB
44.txt AC 168 ms 9044 KB
45.txt AC 168 ms 9044 KB
46.txt AC 172 ms 9044 KB
47.txt WA 177 ms 9044 KB
48.txt AC 177 ms 9044 KB
s1.txt AC 176 ms 9168 KB
s2.txt AC 181 ms 9044 KB
s3.txt AC 184 ms 9168 KB