Submission #105740

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
105740	2019-04-14T09:26:42 Z	Pro_ktmr	Gap (APIO16_gap)	C++14	30 / 100	535 ms	525312 KB

gap

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define MOD 1000000007

#include"gap.h"

//MinMax(LL s, LL t, LL& mn, LL& mx)
//aiのうちs以上の最小の数がmnに、aiのうちt以下の最大値がmxに格納される

//aiの差分のうち最大のものを返す
LL findGap(int T, int N){
	if(T == 1){
		LL m = 0LL;
		LL M = 1000000000000000000LL;
		vector<LL> v;
		for(int i=0; i<(N+1)/2; i++){
			LL tmp1, tmp2;
			MinMax(m, M, &tmp1, &tmp2);
			v.PB(tmp1);
			v.PB(tmp2);
			m = tmp1+1;
			M = tmp2-1;
		}
		sort(v.begin(), v.end());

		LL ans = 0;
		for(int i=1; i<v.size(); i++){
			ans = max(ans, v[i] - v[i-1]);
		}
		return ans;
	}
	if(T == 2){
#define B 10000000000000LL
		queue<pair<LL, LL>> kukan;
		for(int i=0; i<=1000000000000000000LL; i+=B){
			kukan.push(MP(i,i+B-1));
		}
		vector<LL> v;
		while(kukan.size() > 0){
			LL m = kukan.front().first;
			LL M = kukan.front().second;
			kukan.pop();
			LL tmp1, tmp2;
			MinMax(m, M, &tmp1, &tmp2);
			if(tmp1 == -1) continue;
			v.PB(tmp1);
			if(tmp1 == tmp2) continue;
			v.PB(tmp2);

			LL mid = (tmp1+tmp2) / 2;
			kukan.push(MP(tmp1+1, mid));
			kukan.push(MP(mid+1, tmp2-1));
		}
		sort(v.begin(), v.end());
		LL ans = 0;
		for(int i=1; i<v.size(); i++){
			ans = max(ans, v[i] - v[i-1]);
		}
		return ans;
	}
}

Compilation message

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<v.size(); i++){
                ~^~~~~~~~~
gap.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1; i<v.size(); i++){
                ~^~~~~~~~~
gap.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	3 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	3 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	3 ms	384 KB	Output is correct
16	Correct	17 ms	896 KB	Output is correct
17	Correct	15 ms	896 KB	Output is correct
18	Correct	22 ms	896 KB	Output is correct
19	Correct	16 ms	896 KB	Output is correct
20	Correct	12 ms	896 KB	Output is correct
21	Correct	59 ms	2288 KB	Output is correct
22	Correct	57 ms	2288 KB	Output is correct
23	Correct	60 ms	2288 KB	Output is correct
24	Correct	59 ms	2288 KB	Output is correct
25	Correct	51 ms	2288 KB	Output is correct
26	Correct	56 ms	2296 KB	Output is correct
27	Correct	61 ms	2216 KB	Output is correct
28	Correct	53 ms	2260 KB	Output is correct
29	Correct	52 ms	2252 KB	Output is correct
30	Correct	44 ms	2288 KB	Output is correct
31	Correct	2 ms	384 KB	Output is correct
32	Correct	2 ms	384 KB	Output is correct

Subtask #2

0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	494 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
2	Runtime error	399 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Runtime error	444 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
4	Runtime error	428 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Runtime error	492 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
6	Runtime error	466 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	491 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	440 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	423 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	469 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
11	Runtime error	434 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
12	Runtime error	449 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
13	Runtime error	428 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
14	Runtime error	477 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
15	Runtime error	534 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
16	Runtime error	477 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
17	Runtime error	481 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
18	Runtime error	484 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
19	Runtime error	493 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
20	Runtime error	448 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
21	Runtime error	505 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
22	Runtime error	484 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
23	Runtime error	531 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
24	Runtime error	446 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Runtime error	492 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
26	Runtime error	478 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
27	Runtime error	535 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
28	Runtime error	445 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
29	Runtime error	500 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Runtime error	509 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
31	Runtime error	518 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
32	Runtime error	463 ms	525312 KB	Execution killed with signal 9 (could be triggered by violating memory limits)