답안 #398596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398596	2021-05-04T15:16:09 Z	richyrich	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	1000 ms	30820 KB

shoes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9+7;
const ll N = 2e5+10;
const ll inf = 1e9+100;
const double eps = 1;
int n, a[N];
set<int> L[N], R[N];
ll ans;
long long count_swaps(std::vector<int> s) {
	/*for(int c : s) printf("%d ", c);
	printf("\n");*/
	ans = 0;
    n = s.size();
    for(int i = 1;i <= n;i++) {
    	a[i] = s[i-1];
    	if(a[i] < 0) L[-a[i]].insert(i);
    	else R[a[i]].insert(i);
    }
    /*for(int i = 1; i <= 2; i++) {
    	printf("left %d:", i);
    	for(int c : L[i]) printf("%d ", c);
    	printf("\n");
    }
    for(int i = 1; i <= 2; i++) {
    	printf("right %d:", i);
    	for(int c : R[i]) printf("%d ", c);
    	printf("\n");
    }*/
    for(int i = 1; i <= n; i += 2){
    	int pos, req;
    	if(a[i] < 0) {
    		pos = *R[-a[i]].begin();
    		L[-a[i]].erase(i);
    		R[-a[i]].erase(pos);
    		req = i+1;
    	}
    	else {
    		pos = *L[a[i]].begin();
    		R[a[i]].erase(i);
    		L[a[i]].erase(pos);
    		req = i;
    	}
    	for(int j = pos - 1; j > i; j--) {
    		if(a[j] < 0) {
    			L[-a[j]].erase(j);
    			L[-a[j]].insert(j+1);
    		}
    		else {
    			R[a[j]].erase(j);
    			R[a[j]].insert(j+1);
    		}
    	}
    	for(int j = pos; j > req; j--) {
    		ans++;
    		swap(a[j], a[j-1]);
    	}
    }
    return ans;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19020 KB	Output is correct
2	Correct	11 ms	19040 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19020 KB	Output is correct
2	Correct	11 ms	19040 KB	Output is correct
3	Correct	10 ms	18988 KB	Output is correct
4	Correct	10 ms	19076 KB	Output is correct
5	Correct	11 ms	19020 KB	Output is correct
6	Correct	11 ms	19088 KB	Output is correct
7	Correct	11 ms	19020 KB	Output is correct
8	Correct	11 ms	19020 KB	Output is correct
9	Correct	11 ms	19072 KB	Output is correct
10	Correct	10 ms	19008 KB	Output is correct
11	Correct	10 ms	19052 KB	Output is correct
12	Correct	10 ms	19084 KB	Output is correct
13	Correct	10 ms	19020 KB	Output is correct
14	Correct	14 ms	19020 KB	Output is correct
15	Correct	11 ms	19020 KB	Output is correct
16	Correct	10 ms	19020 KB	Output is correct
17	Correct	10 ms	19020 KB	Output is correct
18	Correct	11 ms	19068 KB	Output is correct
19	Correct	11 ms	18972 KB	Output is correct
20	Correct	11 ms	19020 KB	Output is correct
21	Correct	11 ms	18968 KB	Output is correct
22	Correct	11 ms	19088 KB	Output is correct
23	Correct	10 ms	19020 KB	Output is correct
24	Correct	10 ms	19020 KB	Output is correct
25	Correct	10 ms	19048 KB	Output is correct
26	Correct	12 ms	19072 KB	Output is correct
27	Correct	11 ms	19020 KB	Output is correct
28	Correct	11 ms	19020 KB	Output is correct
29	Correct	11 ms	19020 KB	Output is correct
30	Correct	10 ms	19020 KB	Output is correct
31	Correct	10 ms	19020 KB	Output is correct
32	Correct	10 ms	19064 KB	Output is correct
33	Correct	11 ms	19020 KB	Output is correct
34	Correct	11 ms	19020 KB	Output is correct
35	Correct	12 ms	19020 KB	Output is correct
36	Correct	11 ms	18984 KB	Output is correct

Subtask #3
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19020 KB	Output is correct
2	Correct	11 ms	19040 KB	Output is correct
3	Correct	12 ms	19020 KB	Output is correct
4	Correct	11 ms	19020 KB	Output is correct
5	Correct	11 ms	19020 KB	Output is correct
6	Correct	11 ms	18980 KB	Output is correct
7	Correct	11 ms	19020 KB	Output is correct
8	Correct	10 ms	19088 KB	Output is correct
9	Correct	11 ms	19020 KB	Output is correct
10	Correct	10 ms	19020 KB	Output is correct
11	Correct	12 ms	19020 KB	Output is correct
12	Correct	11 ms	19020 KB	Output is correct
13	Correct	11 ms	18996 KB	Output is correct
14	Correct	10 ms	19056 KB	Output is correct
15	Correct	11 ms	18980 KB	Output is correct
16	Correct	11 ms	18984 KB	Output is correct
17	Correct	12 ms	19020 KB	Output is correct
18	Correct	15 ms	19148 KB	Output is correct
19	Correct	16 ms	19092 KB	Output is correct
20	Correct	77 ms	20188 KB	Output is correct
21	Correct	106 ms	20240 KB	Output is correct
22	Execution timed out	1093 ms	30820 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19020 KB	Output is correct
2	Correct	11 ms	19084 KB	Output is correct
3	Correct	11 ms	19020 KB	Output is correct
4	Correct	11 ms	19020 KB	Output is correct
5	Execution timed out	1082 ms	30756 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19020 KB	Output is correct
2	Correct	11 ms	19040 KB	Output is correct
3	Correct	10 ms	18988 KB	Output is correct
4	Correct	10 ms	19076 KB	Output is correct
5	Correct	11 ms	19020 KB	Output is correct
6	Correct	11 ms	19088 KB	Output is correct
7	Correct	11 ms	19020 KB	Output is correct
8	Correct	11 ms	19020 KB	Output is correct
9	Correct	11 ms	19072 KB	Output is correct
10	Correct	10 ms	19008 KB	Output is correct
11	Correct	10 ms	19052 KB	Output is correct
12	Correct	10 ms	19084 KB	Output is correct
13	Correct	10 ms	19020 KB	Output is correct
14	Correct	14 ms	19020 KB	Output is correct
15	Correct	11 ms	19020 KB	Output is correct
16	Correct	10 ms	19020 KB	Output is correct
17	Correct	10 ms	19020 KB	Output is correct
18	Correct	11 ms	19068 KB	Output is correct
19	Correct	11 ms	18972 KB	Output is correct
20	Correct	11 ms	19020 KB	Output is correct
21	Correct	11 ms	18968 KB	Output is correct
22	Correct	11 ms	19088 KB	Output is correct
23	Correct	10 ms	19020 KB	Output is correct
24	Correct	10 ms	19020 KB	Output is correct
25	Correct	10 ms	19048 KB	Output is correct
26	Correct	12 ms	19072 KB	Output is correct
27	Correct	11 ms	19020 KB	Output is correct
28	Correct	11 ms	19020 KB	Output is correct
29	Correct	11 ms	19020 KB	Output is correct
30	Correct	10 ms	19020 KB	Output is correct
31	Correct	10 ms	19020 KB	Output is correct
32	Correct	10 ms	19064 KB	Output is correct
33	Correct	11 ms	19020 KB	Output is correct
34	Correct	11 ms	19020 KB	Output is correct
35	Correct	12 ms	19020 KB	Output is correct
36	Correct	11 ms	18984 KB	Output is correct
37	Correct	10 ms	18988 KB	Output is correct
38	Correct	11 ms	19032 KB	Output is correct
39	Correct	11 ms	19016 KB	Output is correct
40	Correct	13 ms	19084 KB	Output is correct
41	Correct	37 ms	19180 KB	Output is correct
42	Correct	12 ms	19148 KB	Output is correct
43	Correct	14 ms	19148 KB	Output is correct
44	Correct	73 ms	19076 KB	Output is correct
45	Correct	15 ms	19148 KB	Output is correct
46	Correct	13 ms	19116 KB	Output is correct
47	Correct	61 ms	19148 KB	Output is correct
48	Correct	52 ms	19148 KB	Output is correct
49	Correct	46 ms	19088 KB	Output is correct
50	Correct	83 ms	19148 KB	Output is correct
51	Correct	69 ms	19192 KB	Output is correct
52	Correct	57 ms	19148 KB	Output is correct

Subtask #6
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	19020 KB	Output is correct
2	Correct	11 ms	19040 KB	Output is correct
3	Correct	10 ms	18988 KB	Output is correct
4	Correct	10 ms	19076 KB	Output is correct
5	Correct	11 ms	19020 KB	Output is correct
6	Correct	11 ms	19088 KB	Output is correct
7	Correct	11 ms	19020 KB	Output is correct
8	Correct	11 ms	19020 KB	Output is correct
9	Correct	11 ms	19072 KB	Output is correct
10	Correct	10 ms	19008 KB	Output is correct
11	Correct	10 ms	19052 KB	Output is correct
12	Correct	10 ms	19084 KB	Output is correct
13	Correct	10 ms	19020 KB	Output is correct
14	Correct	14 ms	19020 KB	Output is correct
15	Correct	11 ms	19020 KB	Output is correct
16	Correct	10 ms	19020 KB	Output is correct
17	Correct	10 ms	19020 KB	Output is correct
18	Correct	11 ms	19068 KB	Output is correct
19	Correct	11 ms	18972 KB	Output is correct
20	Correct	11 ms	19020 KB	Output is correct
21	Correct	11 ms	18968 KB	Output is correct
22	Correct	11 ms	19088 KB	Output is correct
23	Correct	10 ms	19020 KB	Output is correct
24	Correct	10 ms	19020 KB	Output is correct
25	Correct	10 ms	19048 KB	Output is correct
26	Correct	12 ms	19072 KB	Output is correct
27	Correct	11 ms	19020 KB	Output is correct
28	Correct	11 ms	19020 KB	Output is correct
29	Correct	11 ms	19020 KB	Output is correct
30	Correct	10 ms	19020 KB	Output is correct
31	Correct	10 ms	19020 KB	Output is correct
32	Correct	10 ms	19064 KB	Output is correct
33	Correct	11 ms	19020 KB	Output is correct
34	Correct	11 ms	19020 KB	Output is correct
35	Correct	12 ms	19020 KB	Output is correct
36	Correct	11 ms	18984 KB	Output is correct
37	Correct	12 ms	19020 KB	Output is correct
38	Correct	11 ms	19020 KB	Output is correct
39	Correct	11 ms	19020 KB	Output is correct
40	Correct	11 ms	18980 KB	Output is correct
41	Correct	11 ms	19020 KB	Output is correct
42	Correct	10 ms	19088 KB	Output is correct
43	Correct	11 ms	19020 KB	Output is correct
44	Correct	10 ms	19020 KB	Output is correct
45	Correct	12 ms	19020 KB	Output is correct
46	Correct	11 ms	19020 KB	Output is correct
47	Correct	11 ms	18996 KB	Output is correct
48	Correct	10 ms	19056 KB	Output is correct
49	Correct	11 ms	18980 KB	Output is correct
50	Correct	11 ms	18984 KB	Output is correct
51	Correct	12 ms	19020 KB	Output is correct
52	Correct	15 ms	19148 KB	Output is correct
53	Correct	16 ms	19092 KB	Output is correct
54	Correct	77 ms	20188 KB	Output is correct
55	Correct	106 ms	20240 KB	Output is correct
56	Execution timed out	1093 ms	30820 KB	Time limit exceeded
57	Halted	0 ms	0 KB	-

답안 #398596

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 20.0 / 20.0

Subtask #3 0 / 20.0

Subtask #4 0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #6 0 / 15.0

Subtask #1
10.0 / 10.0

Subtask #2
20.0 / 20.0

Subtask #3
0 / 20.0

Subtask #4
0 / 15.0

Subtask #5
20.0 / 20.0

Subtask #6
0 / 15.0