Submission #1515707
Source Code Expand
#include <bits/stdc++.h>
#include <math.h>
#define uint unsigned long long
#define ll long long
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
using namespace std;
inline int read()
{
int x = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
const int N = 100010;
const int mod = 1e9 + 7;
ll a[N], b[N], aa[N], bb[N];
map<ll, int> Mp;
vector<int> p;
bool vis[N];
int main()
{
int n,ans = 0;
rep(i, 2, N - 1)
if (!vis[i])
{
p.push_back(i);
for (int j = i + i; j < N; j += i) vis[j] = 1;
}
cin >> n;
rep(i, 0, n - 1)
{
cin >> a[i];
b[i] = a[i];
}
rep(i, 0, n - 1)
{
aa[i] = 1, bb[i] = 1;
int nn = p.size();
rep(j, 0, nn - 1)
{
int cnt = 0;
while (a[i] % p[j] == 0)
{
a[i] /= p[j];
cnt ++;
}
if (cnt % 3 == 1) aa[i] *= p[j], bb[i] *= p[j] * p[j];
else if (cnt % 3 == 2) bb[i] *= p[j], aa[i] *= p[j] * p[j];
}
aa[i] *= a[i];
ll t = floor(sqrt(a[i] * 1.0));
if (t * t == a[i]) bb[i] *= t;
else
{
if (bb[i] * a[i] > 0 && bb[i] * a[i] * a[i] > 0) bb[i] *= a[i] * a[i];
else bb[i] = 0;
}
Mp[aa[i]] ++;
}
int flag = 0;
rep(i, 0, n - 1)
{
if (aa[i] == 1)
{
if (flag == 0) ans ++, flag = 1;
}
else ans += max(Mp[aa[i]], Mp[bb[i]]), Mp[aa[i]] = Mp[bb[i]] = 0;
}
cout << ans;
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Wanna go back home |
User |
lzr156 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2119 Byte |
Status |
WA |
Exec Time |
2 ms |
Memory |
512 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt, s3.txt, s4.txt |
All |
01.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 13.txt, 15.txt, s1.txt, s2.txt, s3.txt, s4.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
WA |
2 ms |
512 KB |
04.txt |
WA |
2 ms |
384 KB |
05.txt |
WA |
2 ms |
384 KB |
06.txt |
WA |
2 ms |
384 KB |
07.txt |
WA |
2 ms |
384 KB |
08.txt |
WA |
2 ms |
384 KB |
09.txt |
WA |
2 ms |
512 KB |
10.txt |
WA |
2 ms |
512 KB |
11.txt |
WA |
2 ms |
384 KB |
13.txt |
WA |
2 ms |
512 KB |
15.txt |
WA |
2 ms |
384 KB |
s1.txt |
WA |
2 ms |
384 KB |
s2.txt |
WA |
2 ms |
384 KB |
s3.txt |
WA |
2 ms |
512 KB |
s4.txt |
WA |
2 ms |
384 KB |