Submission #846821


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);
            HashSet<Long> prs2 = new HashSet<>();
            for (int p : pr) prs2.add((long) p * (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 if (prs2.contains(x)) {
                    y *= x;
                    long s = (long) Math.sqrt(x) - 3;
                    if (s < 0) s = 0;
                    while (s * s < x) ++s;
                    oy *= s;
                } else {
                    for (int p : pr) {
                        if (p > x) break;
                        if (p > 4000) {
//                        long up = (long)Math.pow(2E10 / x, 2.0 / 3.0) + 10;
//                        if (p > up) break;
                            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 7606 Byte
Status WA
Exec Time 2166 ms
Memory 47948 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 3
AC × 49
WA × 2
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 2094 ms 45080 KB
02.txt AC 2117 ms 45212 KB
03.txt AC 2136 ms 45956 KB
04.txt AC 2021 ms 44980 KB
05.txt AC 1869 ms 43628 KB
06.txt AC 2010 ms 43708 KB
07.txt AC 1977 ms 43492 KB
08.txt AC 2166 ms 46544 KB
09.txt AC 1958 ms 43940 KB
10.txt AC 2131 ms 46256 KB
11.txt AC 1413 ms 25676 KB
12.txt AC 1401 ms 25500 KB
13.txt AC 1310 ms 32964 KB
14.txt AC 1315 ms 32908 KB
15.txt AC 1317 ms 32804 KB
16.txt AC 1237 ms 32636 KB
17.txt AC 366 ms 21832 KB
18.txt AC 389 ms 21888 KB
19.txt AC 370 ms 21980 KB
20.txt AC 389 ms 21872 KB
21.txt AC 1461 ms 32996 KB
22.txt WA 1550 ms 32376 KB
23.txt AC 1497 ms 37272 KB
24.txt AC 1517 ms 32372 KB
25.txt AC 1481 ms 32812 KB
26.txt WA 1493 ms 32868 KB
27.txt AC 1161 ms 47948 KB
28.txt AC 262 ms 14800 KB
29.txt AC 278 ms 16000 KB
30.txt AC 285 ms 15884 KB
31.txt AC 281 ms 15892 KB
32.txt AC 297 ms 15332 KB
33.txt AC 190 ms 10708 KB
34.txt AC 378 ms 21960 KB
35.txt AC 382 ms 21920 KB
36.txt AC 189 ms 10580 KB
37.txt AC 1829 ms 30516 KB
38.txt AC 1838 ms 31276 KB
39.txt AC 1809 ms 30964 KB
40.txt AC 1797 ms 27112 KB
41.txt AC 191 ms 10708 KB
42.txt AC 189 ms 10704 KB
43.txt AC 190 ms 10452 KB
44.txt AC 193 ms 10580 KB
45.txt AC 186 ms 10324 KB
46.txt AC 244 ms 10452 KB
47.txt AC 190 ms 10708 KB
48.txt AC 189 ms 10580 KB
s1.txt AC 185 ms 10452 KB
s2.txt AC 192 ms 10580 KB
s3.txt AC 189 ms 10580 KB