답안 #157523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157523	2019-10-12T07:21:00 Z	tevdore	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	594 ms	410184 KB

shoes

#include<bits/stdc++.h>
#define mid (L+R)/2
using namespace std;
int i,ans,k;
int f[300001],sg[1000001];
queue<int>q1[300001];
queue<int>q2[300001];
vector<int>s;
void upd(int u,int L,int R,int pos,int y){
	if(R < pos || L > pos)return;
	if(R == L){sg[u]=y;return;}
	else{
		upd(u*2,L,mid,pos,y);
		upd(u*2+1,mid+1,R,pos,y);
		sg[u]=sg[u*2]+sg[u*2+1];
	}
}
int get(int u,int L,int R,int a,int b){
	if(b < L || a > R)return 0;
	if(a <= L && b >= R)return sg[u];
	return(get(u*2,L,mid,a,b)+get(u*2+1,mid+1,R,a,b));
}
int count_swaps(std:: vector<int>s){
    int n=s.size();
    for(i=0;i<s.size();i++){
        f[i+1]=s[i];
    }
    for(i=1;i<=n;i++){
        upd(1,1,n,i,1);
    }
    for(i=1;i<=n;i++){
		if(f[i] < 0){
		    k=-(f[i]);
			if(q2[k].size() == 0){
				q1[k].push(i);
				continue;
			}
			ans+=get(1,1,n,q2[k].front(),i)-1;
			upd(1,1,n,q2[k].front(),2);
			upd(1,1,n,i,0);
			q2[k].pop();
		}
		if(f[i] > 0){
		    k=f[i];
			if(q1[k].size() == 0){
				q2[k].push(i);
				continue;
			}
			ans+=get(1,1,n,q1[k].front(),i)-2;
			upd(1,1,n,q1[k].front(),2);
			upd(1,1,n,i,0);
			q1[k].pop();
		}
	}
	return ans;
}

Compilation message

shoes.cpp: In function 'int count_swaps(std::vector<int>)':
shoes.cpp:25:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<s.size();i++){
             ~^~~~~~~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	404216 KB	Output is correct
2	Correct	432 ms	404292 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	404216 KB	Output is correct
2	Correct	432 ms	404292 KB	Output is correct
3	Correct	419 ms	404276 KB	Output is correct
4	Correct	421 ms	404268 KB	Output is correct
5	Correct	420 ms	404520 KB	Output is correct
6	Correct	507 ms	404160 KB	Output is correct
7	Correct	420 ms	404380 KB	Output is correct
8	Correct	415 ms	404216 KB	Output is correct
9	Correct	419 ms	404380 KB	Output is correct
10	Correct	420 ms	404312 KB	Output is correct
11	Correct	419 ms	404216 KB	Output is correct
12	Correct	419 ms	404308 KB	Output is correct
13	Correct	424 ms	404256 KB	Output is correct
14	Correct	420 ms	404472 KB	Output is correct
15	Correct	421 ms	404276 KB	Output is correct
16	Correct	420 ms	404308 KB	Output is correct
17	Correct	421 ms	404316 KB	Output is correct
18	Correct	424 ms	404344 KB	Output is correct
19	Correct	424 ms	404344 KB	Output is correct
20	Correct	436 ms	404384 KB	Output is correct
21	Correct	440 ms	404556 KB	Output is correct
22	Correct	421 ms	404348 KB	Output is correct
23	Correct	420 ms	404220 KB	Output is correct
24	Correct	421 ms	404240 KB	Output is correct
25	Correct	428 ms	404192 KB	Output is correct
26	Correct	421 ms	404240 KB	Output is correct
27	Correct	422 ms	404348 KB	Output is correct
28	Correct	420 ms	404344 KB	Output is correct
29	Correct	424 ms	404344 KB	Output is correct
30	Correct	422 ms	404260 KB	Output is correct
31	Correct	416 ms	404216 KB	Output is correct
32	Correct	418 ms	404216 KB	Output is correct
33	Correct	418 ms	404344 KB	Output is correct
34	Correct	424 ms	404264 KB	Output is correct
35	Correct	414 ms	404188 KB	Output is correct
36	Correct	554 ms	404344 KB	Output is correct

Subtask #3

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	404216 KB	Output is correct
2	Correct	432 ms	404292 KB	Output is correct
3	Correct	494 ms	404236 KB	Output is correct
4	Correct	523 ms	404360 KB	Output is correct
5	Correct	525 ms	404216 KB	Output is correct
6	Correct	434 ms	404388 KB	Output is correct
7	Correct	420 ms	404216 KB	Output is correct
8	Correct	417 ms	404344 KB	Output is correct
9	Correct	422 ms	404236 KB	Output is correct
10	Correct	421 ms	404352 KB	Output is correct
11	Correct	477 ms	404248 KB	Output is correct
12	Correct	434 ms	404304 KB	Output is correct
13	Correct	424 ms	404344 KB	Output is correct
14	Correct	421 ms	404212 KB	Output is correct
15	Correct	415 ms	404244 KB	Output is correct
16	Correct	482 ms	404276 KB	Output is correct
17	Correct	457 ms	404336 KB	Output is correct
18	Correct	464 ms	404320 KB	Output is correct
19	Correct	467 ms	404344 KB	Output is correct
20	Correct	465 ms	404728 KB	Output is correct
21	Correct	451 ms	404824 KB	Output is correct
22	Correct	584 ms	408708 KB	Output is correct
23	Correct	582 ms	409936 KB	Output is correct
24	Correct	564 ms	409968 KB	Output is correct
25	Incorrect	570 ms	410184 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	415 ms	404216 KB	Output is correct
2	Correct	420 ms	404344 KB	Output is correct
3	Correct	414 ms	404192 KB	Output is correct
4	Correct	420 ms	404288 KB	Output is correct
5	Incorrect	594 ms	408716 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	404216 KB	Output is correct
2	Correct	432 ms	404292 KB	Output is correct
3	Correct	419 ms	404276 KB	Output is correct
4	Correct	421 ms	404268 KB	Output is correct
5	Correct	420 ms	404520 KB	Output is correct
6	Correct	507 ms	404160 KB	Output is correct
7	Correct	420 ms	404380 KB	Output is correct
8	Correct	415 ms	404216 KB	Output is correct
9	Correct	419 ms	404380 KB	Output is correct
10	Correct	420 ms	404312 KB	Output is correct
11	Correct	419 ms	404216 KB	Output is correct
12	Correct	419 ms	404308 KB	Output is correct
13	Correct	424 ms	404256 KB	Output is correct
14	Correct	420 ms	404472 KB	Output is correct
15	Correct	421 ms	404276 KB	Output is correct
16	Correct	420 ms	404308 KB	Output is correct
17	Correct	421 ms	404316 KB	Output is correct
18	Correct	424 ms	404344 KB	Output is correct
19	Correct	424 ms	404344 KB	Output is correct
20	Correct	436 ms	404384 KB	Output is correct
21	Correct	440 ms	404556 KB	Output is correct
22	Correct	421 ms	404348 KB	Output is correct
23	Correct	420 ms	404220 KB	Output is correct
24	Correct	421 ms	404240 KB	Output is correct
25	Correct	428 ms	404192 KB	Output is correct
26	Correct	421 ms	404240 KB	Output is correct
27	Correct	422 ms	404348 KB	Output is correct
28	Correct	420 ms	404344 KB	Output is correct
29	Correct	424 ms	404344 KB	Output is correct
30	Correct	422 ms	404260 KB	Output is correct
31	Correct	416 ms	404216 KB	Output is correct
32	Correct	418 ms	404216 KB	Output is correct
33	Correct	418 ms	404344 KB	Output is correct
34	Correct	424 ms	404264 KB	Output is correct
35	Correct	414 ms	404188 KB	Output is correct
36	Correct	554 ms	404344 KB	Output is correct
37	Correct	414 ms	404344 KB	Output is correct
38	Correct	419 ms	404216 KB	Output is correct
39	Correct	419 ms	404216 KB	Output is correct
40	Correct	417 ms	404268 KB	Output is correct
41	Correct	421 ms	404344 KB	Output is correct
42	Correct	419 ms	404360 KB	Output is correct
43	Correct	425 ms	404344 KB	Output is correct
44	Correct	421 ms	404472 KB	Output is correct
45	Correct	417 ms	404392 KB	Output is correct
46	Correct	419 ms	404376 KB	Output is correct
47	Correct	420 ms	404344 KB	Output is correct
48	Correct	415 ms	404288 KB	Output is correct
49	Correct	419 ms	404484 KB	Output is correct
50	Correct	458 ms	404216 KB	Output is correct
51	Correct	436 ms	404204 KB	Output is correct
52	Correct	424 ms	404216 KB	Output is correct

Subtask #6

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	421 ms	404216 KB	Output is correct
2	Correct	432 ms	404292 KB	Output is correct
3	Correct	419 ms	404276 KB	Output is correct
4	Correct	421 ms	404268 KB	Output is correct
5	Correct	420 ms	404520 KB	Output is correct
6	Correct	507 ms	404160 KB	Output is correct
7	Correct	420 ms	404380 KB	Output is correct
8	Correct	415 ms	404216 KB	Output is correct
9	Correct	419 ms	404380 KB	Output is correct
10	Correct	420 ms	404312 KB	Output is correct
11	Correct	419 ms	404216 KB	Output is correct
12	Correct	419 ms	404308 KB	Output is correct
13	Correct	424 ms	404256 KB	Output is correct
14	Correct	420 ms	404472 KB	Output is correct
15	Correct	421 ms	404276 KB	Output is correct
16	Correct	420 ms	404308 KB	Output is correct
17	Correct	421 ms	404316 KB	Output is correct
18	Correct	424 ms	404344 KB	Output is correct
19	Correct	424 ms	404344 KB	Output is correct
20	Correct	436 ms	404384 KB	Output is correct
21	Correct	440 ms	404556 KB	Output is correct
22	Correct	421 ms	404348 KB	Output is correct
23	Correct	420 ms	404220 KB	Output is correct
24	Correct	421 ms	404240 KB	Output is correct
25	Correct	428 ms	404192 KB	Output is correct
26	Correct	421 ms	404240 KB	Output is correct
27	Correct	422 ms	404348 KB	Output is correct
28	Correct	420 ms	404344 KB	Output is correct
29	Correct	424 ms	404344 KB	Output is correct
30	Correct	422 ms	404260 KB	Output is correct
31	Correct	416 ms	404216 KB	Output is correct
32	Correct	418 ms	404216 KB	Output is correct
33	Correct	418 ms	404344 KB	Output is correct
34	Correct	424 ms	404264 KB	Output is correct
35	Correct	414 ms	404188 KB	Output is correct
36	Correct	554 ms	404344 KB	Output is correct
37	Correct	494 ms	404236 KB	Output is correct
38	Correct	523 ms	404360 KB	Output is correct
39	Correct	525 ms	404216 KB	Output is correct
40	Correct	434 ms	404388 KB	Output is correct
41	Correct	420 ms	404216 KB	Output is correct
42	Correct	417 ms	404344 KB	Output is correct
43	Correct	422 ms	404236 KB	Output is correct
44	Correct	421 ms	404352 KB	Output is correct
45	Correct	477 ms	404248 KB	Output is correct
46	Correct	434 ms	404304 KB	Output is correct
47	Correct	424 ms	404344 KB	Output is correct
48	Correct	421 ms	404212 KB	Output is correct
49	Correct	415 ms	404244 KB	Output is correct
50	Correct	482 ms	404276 KB	Output is correct
51	Correct	457 ms	404336 KB	Output is correct
52	Correct	464 ms	404320 KB	Output is correct
53	Correct	467 ms	404344 KB	Output is correct
54	Correct	465 ms	404728 KB	Output is correct
55	Correct	451 ms	404824 KB	Output is correct
56	Correct	584 ms	408708 KB	Output is correct
57	Correct	582 ms	409936 KB	Output is correct
58	Correct	564 ms	409968 KB	Output is correct
59	Incorrect	570 ms	410184 KB	Output isn't correct
60	Halted	0 ms	0 KB	-