Submission #65372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
65372	2018-08-07T13:07:13 Z	검수컵(#1978, imsifile)	Key of Impassable Doors (FXCUP3_key)	C++	57 / 100	22 ms	4076 KB

#include "key.h"
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int ba[1010], self[1010], par[1010], ccn, ld[1010];
// par[i] = -x (i is in cycle x), ld[x] = leader of cycle x
vector<int> lds[1010]; // lds[i] : leaders that ba[x]=i

int ExploreKey(vector<int> &v, int s, int e, int pl, int nocall){
	if(!nocall){
		if(pl) TakeKey(pl);
		for(int i=s; i<=e; i++){
			if(v[i]<0) TakeKey(ld[-v[i]]);
			else TakeKey(v[i]);
		}
		return Explore();
	}
	return 0;
}

int cmp(const int &x, const int &y){
	return self[x] < self[y];
}

int para(int ix, vector<int> &v){
	int mi=0, mx=v.size(), md;
	v.push_back(0);
	while(1){
		md = (mi+mx)/2;
		if(mi==mx) break;
		if(ExploreKey(v, mi, md, ix, 0) <= ExploreKey(v, mi, md, 0, 0)+1) mx=md;
		else mi=md+1;
	}
	md = v[md];
	v.pop_back();
	return md;
}

void EnsureKeyInfo(int N) {
	for(int i=1; i<=N; i++){
		TakeKey(i);
		self[i]=Explore();
	}
	for(int i=0; i<N; i++) ba[i]=i+1;
	sort(ba, ba+N, cmp);
	for(int t=0; t<N; t++){
		int i=ba[t];
		par[i]=para(i, lds[self[i]-1]);
		if(par[i]<=0){
			if(par[i]==0){
				par[i]=-(++ccn), ld[ccn]=i;
				if(self[i]>1) lds[self[i]-1].push_back(-ccn);
				lds[self[i]].push_back(i);
			}
		}
		else lds[self[i]].push_back(i);
	}
	for(int i=1; i<=N; i++){
		int t=i;
		for(; par[t]>0; t=par[t]) Report(i, t);
		for(int j=1; j<=N; j++){
			if(par[t] == par[j]) Report(i, j);
		}
	}
}

Subtask #1
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	744 KB	Output is correct
3	Correct	3 ms	904 KB	Output is correct
4	Correct	3 ms	904 KB	Output is correct
5	Correct	2 ms	904 KB	Output is correct
6	Correct	3 ms	928 KB	Output is correct
7	Correct	2 ms	944 KB	Output is correct
8	Correct	3 ms	944 KB	Output is correct
9	Correct	3 ms	944 KB	Output is correct
10	Correct	3 ms	944 KB	Output is correct
11	Correct	3 ms	1032 KB	Output is correct
12	Correct	2 ms	1088 KB	Output is correct
13	Correct	3 ms	1088 KB	Output is correct
14	Correct	2 ms	1088 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	4 ms	1088 KB	Output is correct
17	Correct	3 ms	1088 KB	Output is correct

Subtask #2
34.0 / 34.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	744 KB	Output is correct
3	Correct	3 ms	904 KB	Output is correct
4	Correct	3 ms	904 KB	Output is correct
5	Correct	2 ms	904 KB	Output is correct
6	Correct	3 ms	928 KB	Output is correct
7	Correct	2 ms	944 KB	Output is correct
8	Correct	3 ms	944 KB	Output is correct
9	Correct	3 ms	944 KB	Output is correct
10	Correct	3 ms	944 KB	Output is correct
11	Correct	3 ms	1032 KB	Output is correct
12	Correct	2 ms	1088 KB	Output is correct
13	Correct	3 ms	1088 KB	Output is correct
14	Correct	2 ms	1088 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	4 ms	1088 KB	Output is correct
17	Correct	3 ms	1088 KB	Output is correct
18	Correct	6 ms	1896 KB	Output is correct
19	Correct	6 ms	1896 KB	Output is correct
20	Correct	7 ms	1896 KB	Output is correct
21	Correct	7 ms	1900 KB	Output is correct
22	Correct	6 ms	1900 KB	Output is correct
23	Correct	8 ms	2540 KB	Output is correct
24	Correct	10 ms	2540 KB	Output is correct
25	Correct	11 ms	2568 KB	Output is correct
26	Correct	9 ms	2568 KB	Output is correct
27	Correct	12 ms	2632 KB	Output is correct
28	Correct	12 ms	2632 KB	Output is correct
29	Correct	11 ms	2632 KB	Output is correct
30	Correct	12 ms	2632 KB	Output is correct
31	Correct	9 ms	2632 KB	Output is correct
32	Correct	8 ms	2632 KB	Output is correct
33	Correct	9 ms	2632 KB	Output is correct

Subtask #3
0 / 43.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	744 KB	Output is correct
3	Correct	3 ms	904 KB	Output is correct
4	Correct	3 ms	904 KB	Output is correct
5	Correct	2 ms	904 KB	Output is correct
6	Correct	3 ms	928 KB	Output is correct
7	Correct	2 ms	944 KB	Output is correct
8	Correct	3 ms	944 KB	Output is correct
9	Correct	3 ms	944 KB	Output is correct
10	Correct	3 ms	944 KB	Output is correct
11	Correct	3 ms	1032 KB	Output is correct
12	Correct	2 ms	1088 KB	Output is correct
13	Correct	3 ms	1088 KB	Output is correct
14	Correct	2 ms	1088 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	4 ms	1088 KB	Output is correct
17	Correct	3 ms	1088 KB	Output is correct
18	Correct	6 ms	1896 KB	Output is correct
19	Correct	6 ms	1896 KB	Output is correct
20	Correct	7 ms	1896 KB	Output is correct
21	Correct	7 ms	1900 KB	Output is correct
22	Correct	6 ms	1900 KB	Output is correct
23	Correct	8 ms	2540 KB	Output is correct
24	Correct	10 ms	2540 KB	Output is correct
25	Correct	11 ms	2568 KB	Output is correct
26	Correct	9 ms	2568 KB	Output is correct
27	Correct	12 ms	2632 KB	Output is correct
28	Correct	12 ms	2632 KB	Output is correct
29	Correct	11 ms	2632 KB	Output is correct
30	Correct	12 ms	2632 KB	Output is correct
31	Correct	9 ms	2632 KB	Output is correct
32	Correct	8 ms	2632 KB	Output is correct
33	Correct	9 ms	2632 KB	Output is correct
34	Correct	21 ms	3948 KB	Output is correct
35	Correct	22 ms	3948 KB	Output is correct
36	Runtime error	19 ms	4076 KB	Execution failed because the return code was nonzero
37	Halted	0 ms	0 KB	-

Submission #65372

Compilation message

Subtask #1 23.0 / 23.0

Subtask #2 34.0 / 34.0

Subtask #3 0 / 43.0

Subtask #1
23.0 / 23.0

Subtask #2
34.0 / 34.0

Subtask #3
0 / 43.0