Submission #1531376


Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

//long long tbl[100100];

struct loc {
	long long val;
	int ls,idx;
};

bool operator< (const loc &a, const loc &b) {
	return a.val<b.val;
}

vector<long long> cube;
vector<long long> sq;
vector<loc> work;
vector<long long> ls[100100];
vector<int> cntt[100100];

bool find(vector<long long> &tbl,long long x) {
	return (*lower_bound(tbl.begin(),tbl.end(),x))==x;
}

bool find2(vector<loc> &tbl,long long x,loc &out) {
	auto tmp = lower_bound(tbl.begin(),tbl.end(),loc{x,0,0});
	if (tmp->val==x) {
		out=*tmp;
		return true;
	}
	return false;
}

int mic[1010][2];

int solve(int ls,int x,int sel) {
	if (x==0) return (sel)?cntt[ls][0]:0;
	if (mic[x][sel]!=-1) return mic[x][sel];
	if (sel) {
		return mic[x][sel]=solve(ls,x-1,0);
	} else {
		return mic[x][sel]=max(solve(ls,x-1,0),solve(ls,x-1,1));
	}
}

int main () {
	int n;
	scanf("%d",&n);
	for (long long i=1;i*i*i<=1e10;i++) {
		cube.push_back(i*i*i);
	}
	for (long long i=1;i*i<=1e10;i++) {
		sq.push_back(i*i);
	}
	for (long long i=2;i<1e5;i++) {
		if (find(cube,i)) continue;
		if (find(sq,i)) continue;
		//printf("%lld\n",i);
		for (long long j=i;j<=1e10;j*=j) {
			if (j==0) break;
			//printf("%lld\n",j);
			//scanf("%d",&n);
			work.push_back(loc{j,(int)i,(int)ls[i].size()});
			ls[i].push_back(j);
			cntt[i].push_back(0);
		}
	}
	sort(work.begin(),work.end());
	long long x;
	int ans=0;
	bool cb=false;
	for (int i=0;i<n;i++) {
		scanf("%lld",&x);
		loc now;
		if (find(cube,x)) {
			cb=true;
		} else if (find2(work,x,now)) {
			cntt[now.ls][now.idx]++;
		} else if (x>1e5) {
			ans++;
		}
	}
	for (int i=2;i<=1e5;i++) {
		memset(mic,-1,sizeof(mic));
		if (cntt[i].size()==0) continue;
		int tmp = max(solve(i,cntt[i].size()-1,0),solve(i,cntt[i].size()-1,01));
		ans+=tmp;
		//if (tmp) {
			//for (int j=0;j<(int)cntt[i].size();j++) {
				//printf("%lld, %d, %d, %d\n",ls[i][j],cntt[i][j],mic[j][0],mic[j][1]);
			//}
			//printf("%d %d\n",i,tmp);		
		//}
	}
	printf("%d\n",ans+cb);
	return 0;
}

Submission Info

Submission Time
Task D - Anticube
User milmillin
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2164 Byte
Status WA
Exec Time 97 ms
Memory 16784 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:52:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:77:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&x);
                   ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 3
AC × 26
WA × 25
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 96 ms 16528 KB
02.txt WA 97 ms 16528 KB
03.txt AC 96 ms 16784 KB
04.txt AC 96 ms 16528 KB
05.txt AC 96 ms 16528 KB
06.txt AC 97 ms 16528 KB
07.txt WA 97 ms 16528 KB
08.txt WA 97 ms 16528 KB
09.txt AC 96 ms 16528 KB
10.txt AC 97 ms 16528 KB
11.txt AC 96 ms 16528 KB
12.txt AC 96 ms 16528 KB
13.txt WA 88 ms 16528 KB
14.txt WA 88 ms 16528 KB
15.txt WA 88 ms 16528 KB
16.txt WA 88 ms 16528 KB
17.txt WA 95 ms 16528 KB
18.txt WA 96 ms 16528 KB
19.txt WA 95 ms 16528 KB
20.txt WA 96 ms 16528 KB
21.txt WA 97 ms 16528 KB
22.txt WA 97 ms 16528 KB
23.txt WA 95 ms 16528 KB
24.txt WA 96 ms 16528 KB
25.txt WA 95 ms 16528 KB
26.txt WA 96 ms 16528 KB
27.txt WA 80 ms 16528 KB
28.txt AC 73 ms 16656 KB
29.txt AC 73 ms 16528 KB
30.txt AC 77 ms 16528 KB
31.txt WA 77 ms 16528 KB
32.txt WA 77 ms 16528 KB
33.txt AC 65 ms 16528 KB
34.txt AC 83 ms 16656 KB
35.txt AC 79 ms 16528 KB
36.txt AC 66 ms 16528 KB
37.txt WA 97 ms 16784 KB
38.txt WA 97 ms 16528 KB
39.txt WA 97 ms 16528 KB
40.txt WA 97 ms 16528 KB
41.txt WA 65 ms 16528 KB
42.txt AC 65 ms 16528 KB
43.txt AC 65 ms 16528 KB
44.txt AC 65 ms 16528 KB
45.txt AC 65 ms 16528 KB
46.txt AC 65 ms 16528 KB
47.txt AC 65 ms 16528 KB
48.txt AC 65 ms 16656 KB
s1.txt AC 65 ms 16528 KB
s2.txt AC 65 ms 16528 KB
s3.txt AC 68 ms 16656 KB