Submission #846417


Source Code Expand

Copy
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.HashSet;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

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

    static class TaskD {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();
            //int n = 1000 * 100;
            int[] pr = PrimesGenerator.getPrimes(101000);
            HashSet<Long> prs = new HashSet<>();
            for (int p : pr) prs.add((long) p);
            HashMap<Long, Integer> d = new HashMap<>();
            HashMap<Long, Long> op = new HashMap<>();
            for (int i = 0; i < n; ++i) {
                long x = in.nextLong();
                //long x = 9999999967L;
                long y = 1, oy = 1;
                if (prs.contains(x)) {
                    y *= x;
                    oy *= x;
                    oy *= x;
                } else {
                    long up = (long) Math.pow(2E10 / x, 3.0 / 3.0) + 10;
                    for (int p : pr) {
                        if (p > x) break;
                        if (p > up) break;
                        int c = 0;
                        while (x % p == 0) {
                            x /= p;
                            ++c;
                        }
                        c %= 3;
                        if (c == 0) continue;
                        if (c == 1) {
                            y *= p;
                            oy *= p;
                            oy *= p;
                        } else {
                            y *= p;
                            y *= p;
                            oy *= p;
                        }
                    }
                    if (x != 1) {
                        y *= x;
                        oy = 0;
                    }
                }


                if (d.containsKey(y)) {
                    d.put(y, d.get(y) + 1);
                } else {
                    d.put(y, 1);
                    op.put(y, oy);
                }
            }

            HashSet<Long> used = new HashSet<>();
            int res = 0;
            for (long x : d.keySet()) {
                if (x == 1) {
                    ++res;
                    continue;
                }
                if (used.contains(x)) continue;
                long ox = op.get(x);
                int val = d.get(x);
                int oval = d.containsKey(ox) ? d.get(ox) : 0;
                res += Math.max(val, oval);
                used.add(x);
                used.add(ox);
            }
            out.printLine(res);
        }

    }

    static class PrimesGenerator {
        public static int[] getPrimes(int n) {
            boolean[] prime = new boolean[n + 1];
            Arrays.fill(prime, 2, n + 1, true);
            for (int i = 2; i * i <= n; i++) {
                if (prime[i]) {
                    for (int j = i * i; j <= n; j += i) {
                        prime[j] = false;
                    }
                }
            }
            int[] primes = new int[n + 1];
            int cnt = 0;
            for (int i = 0; i < prime.length; i++)
                if (prime[i])
                    primes[cnt++] = i;

            return Arrays.copyOf(primes, cnt);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

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

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buffer = new byte[10000];
        private int cur;
        private int count;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isSpace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (count == -1) {
                throw new InputMismatchException();
            }
            try {
                if (cur >= count) {
                    cur = 0;
                    count = stream.read(buffer);
                    if (count <= 0)
                        return -1;
                }
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            return buffer[cur++];
        }

        public int readSkipSpace() {
            int c;
            do {
                c = read();
            } while (isSpace(c));
            return c;
        }

        public int nextInt() {
            int sgn = 1;
            int c = readSkipSpace();
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = res * 10 + c - '0';
                c = read();
            } while (!isSpace(c));
            res *= sgn;
            return res;
        }

        public long nextLong() {
            long sgn = 1;
            int c = readSkipSpace();
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res = res * 10L + (long) (c - '0');
                c = read();
            } while (!isSpace(c));
            res *= sgn;
            return res;
        }

    }
}

Submission Info

Submission Time
Task D - Anticube
User ilyakor
Language Java8 (OpenJDK 1.8.0)
Score 0
Code Size 7134 Byte
Status WA
Exec Time 5260 ms
Memory 48144 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 3
AC × 37
WA × 10
TLE × 4
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 AC 553 ms 39756 KB
02.txt AC 564 ms 41612 KB
03.txt AC 549 ms 41252 KB
04.txt AC 649 ms 40608 KB
05.txt AC 565 ms 39912 KB
06.txt AC 606 ms 39868 KB
07.txt AC 620 ms 40368 KB
08.txt AC 574 ms 40668 KB
09.txt AC 546 ms 40576 KB
10.txt AC 543 ms 40380 KB
11.txt AC 391 ms 26656 KB
12.txt AC 425 ms 26048 KB
13.txt TLE 5257 ms 21676 KB
14.txt TLE 5260 ms 23388 KB
15.txt TLE 5256 ms 22152 KB
16.txt TLE 5260 ms 18784 KB
17.txt AC 381 ms 21408 KB
18.txt AC 375 ms 20540 KB
19.txt AC 361 ms 19976 KB
20.txt AC 373 ms 19680 KB
21.txt WA 4337 ms 36072 KB
22.txt WA 4558 ms 36252 KB
23.txt WA 4587 ms 35872 KB
24.txt WA 4293 ms 32804 KB
25.txt WA 4462 ms 37784 KB
26.txt WA 4386 ms 36048 KB
27.txt AC 1781 ms 48144 KB
28.txt AC 277 ms 14036 KB
29.txt AC 281 ms 14932 KB
30.txt AC 296 ms 15060 KB
31.txt AC 351 ms 14700 KB
32.txt AC 288 ms 14992 KB
33.txt AC 185 ms 9680 KB
34.txt AC 346 ms 17488 KB
35.txt AC 366 ms 17720 KB
36.txt AC 193 ms 9684 KB
37.txt WA 1093 ms 26208 KB
38.txt WA 1094 ms 30072 KB
39.txt WA 1085 ms 27372 KB
40.txt WA 1077 ms 26308 KB
41.txt AC 183 ms 10064 KB
42.txt AC 191 ms 9744 KB
43.txt AC 180 ms 9812 KB
44.txt AC 184 ms 9684 KB
45.txt AC 191 ms 9812 KB
46.txt AC 190 ms 9940 KB
47.txt AC 186 ms 9680 KB
48.txt AC 189 ms 9812 KB
s1.txt AC 187 ms 9812 KB
s2.txt AC 186 ms 9676 KB
s3.txt AC 185 ms 9808 KB