Submission #846676


Source Code Expand

Copy
// {{{ by shik
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int N=1e5+10;

bitset<N> p_tbl;
vector<int> primes;
void sieve() {
    p_tbl[1]=1;
    for ( int i=2; i<N; i++ ) {
        if ( !p_tbl[i] ) primes.push_back(i);
        for ( int p:primes ) {
            int x=i*p;
            if ( x>=N ) break;
            p_tbl[x]=1;
            if ( i%p==0 ) break;
        }
    }
}

int n;
uint64_t a[N],b1[N],b2[N];
int main() {
    sieve();
    R(n);
    REP(i,n) scanf("%llu",a+i);
    sort(a,a+n);
    // n=10000;
    // REP(i,n) a[i]=1; //rand();
    REP(i,n) {
        if ( i>0 && a[i]==a[i-1] ) {
            b1[i]=b1[i-1];
            b2[i]=b2[i-1];
            continue;
        }
        if ( i%1000==0 ) dump(i);
        VI f;
        uint64_t x1=1,x2=1;
        for ( int p:primes ) {
            if ( 1ULL*p*p>a[i] ) break;
            if ( a[i]%p!=0 ) continue;
            a[i]/=p;
            int x=1;
            while ( a[i]%p==0 ) {
                x++;
                a[i]/=p;
            }
            x%=3;
            REP(j,x) x1*=p;
            REP(j,(3-x)%3) x2*=p;
        }
        if ( a[i]!=1 ) {
            x1*=a[i];
            x2*=a[i]*a[i]; // overflow :D
        }
        b1[i]=x1;
        b2[i]=x2;
    }
    map<uint64_t,int> mp;
    REP(i,n) mp[b1[i]]++;
    int ans=0;
    REP(i,n) {
        if ( b1[i]!=b2[i] && tie(mp[b1[i]],b1[i])>tie(mp[b2[i]],b2[i]) ) ans++;
    }
    if ( mp[1] ) ans++;
    W(ans);
    return 0;
}

Submission Info

Submission Time
Task D - Anticube
User shik
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 4343 Byte
Status
Exec Time 3871 ms
Memory 15104 KB

Compile Error

./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:63:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                              ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:127:30: warning: format ‘%llu’ expects argument of type ‘long long unsigned int*’, but argument 2 has type ‘uint64_t* {aka long unsigned int*}’ [-Wformat=]
     REP(i,n) scanf("%llu",a+i);
                              ^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:62:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( int &x ) { scanf("%d",&x); }
                                   ^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:63:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( long...

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 1100 / 1100 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 2101 ms 15104 KB
02.txt 2122 ms 15104 KB
03.txt 2115 ms 15104 KB
04.txt 2113 ms 15104 KB
05.txt 2085 ms 15104 KB
06.txt 2097 ms 15104 KB
07.txt 2077 ms 15104 KB
08.txt 2116 ms 15104 KB
09.txt 2114 ms 15104 KB
10.txt 2091 ms 15104 KB
11.txt 3871 ms 6528 KB
12.txt 3830 ms 6528 KB
13.txt 1463 ms 6528 KB
14.txt 1483 ms 6528 KB
15.txt 1489 ms 6528 KB
16.txt 1494 ms 6528 KB
17.txt 91 ms 2688 KB
18.txt 92 ms 2688 KB
19.txt 91 ms 2688 KB
20.txt 90 ms 2688 KB
21.txt 3014 ms 10112 KB
22.txt 3032 ms 10112 KB
23.txt 3011 ms 10112 KB
24.txt 3022 ms 10112 KB
25.txt 3052 ms 10112 KB
26.txt 2993 ms 10112 KB
27.txt 185 ms 12928 KB
28.txt 24 ms 2688 KB
29.txt 32 ms 2688 KB
30.txt 35 ms 2688 KB
31.txt 34 ms 2688 KB
32.txt 34 ms 2688 KB
33.txt 6 ms 384 KB
34.txt 92 ms 2688 KB
35.txt 83 ms 2688 KB
36.txt 5 ms 384 KB
37.txt 3853 ms 7424 KB
38.txt 3850 ms 7424 KB
39.txt 3823 ms 7424 KB
40.txt 3836 ms 7424 KB
41.txt 5 ms 384 KB
42.txt 6 ms 384 KB
43.txt 5 ms 384 KB
44.txt 5 ms 384 KB
45.txt 5 ms 384 KB
46.txt 5 ms 384 KB
47.txt 6 ms 384 KB
48.txt 6 ms 384 KB
s1.txt 6 ms 384 KB
s2.txt 5 ms 384 KB
s3.txt 5 ms 384 KB