Submission #991718

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
991718	2024-06-02T21:41:37 Z	aryan12	Magic Show (APIO24_show)	C++17	35 / 100	4 ms	1508 KB

Alice

#include "Alice.h"
#include <bits/stdc++.h>
using namespace std;

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

long long par[5000];

long long find(long long x) {
	if(x == par[x]) {
		return x;
	}
	return find(par[x]);
}

void unite(long long a, long long b) {
	a = find(a);
	b = find(b);
	if(a == b) return;
	par[a] = b;
}

vector<pair<int,int> > Alice() {
	// add your code here
	
	// change below into your code
	iota(par, par + 5000, 0);
    long long x = setN(5000);
    long long center1 = (x - 1) / 5000;
    long long center2 = (x - 1) % 5000;
    long long center3 = (center2 - center1 + 5000) % 5000;
    vector<pair<int, int> > edges;
    for(long long i = 0; i < 1667; i++) {
    	if(center1 != i) {
    		if(find(center1) != find(i)) {
    			edges.push_back({center1 + 1, i + 1});
    			unite(i, center1);
    		}
    	}
    }
    for(long long i = 1667; i < 3334; i++) {
    	if(center2 != i) {
    		if(find(center2) != find(i)) {
    			edges.push_back({center2 + 1, i + 1});
    			unite(i, center2);
    		}
    	}	
    }
    for(long long i = 3334; i < 5000; i++) {
    	if(center3 != i) {
    		if(find(center3) != find(i)) {
    			edges.push_back({center3 + 1, i + 1});
    			unite(i, center3);
    		}
    	}
    }
    long long prev_same = -1;
    for(long long i = 0; i < 5000; i++) {
    	if(find(i) == i) {
    		if(prev_same != -1) {
    			edges.push_back({prev_same + 1, i + 1});
    		}
    		prev_same = i;
    	}
    }
    return edges;
}

Bob

#include "Bob.h"
#include <bits/stdc++.h>
using namespace std;

// you may define some global variables, but it does not work if you try to transfer any information from function Alice() to function Bob() through these variables.
// you had better not use the same global variables in function Alice() and in function Bob().

long long Bob(vector<pair<int,int> > V) {
	long long center1 = -1, center2 = -1, center3 = -1;
	vector<long long> g[5000];
	for(auto [u, v]: V) {
		g[u - 1].push_back(v - 1);
		g[v - 1].push_back(u - 1);
	}
	for(long long i = 0; i < 5000; i++) {
		long long cnt1 = 0, cnt2 = 0, cnt3 = 0;
		for(auto j: g[i]) {
			if(j < 1667) {
				cnt1 += 1;
			}
			else if(j < 3334) {
				cnt2 += 1;
			}
			else {
				cnt3 += 1;
			}
		}
		if(cnt1 >= 10) {
			center1 = i;
		}
		if(cnt2 >= 10) {
			center2 = i;
		}
		if(cnt3 >= 10) {
			center3 = i;
		}
	}
	if(center1 != -1 && center2 != -1) {
		long long ans = center1 * 5000 + center2;
		return ans + 1;
	}
	if(center1 != -1 && center3 != -1) {
		long long center2 = (center1 + center3) % 5000;
		long long ans = center1 * 5000 + center2;
		return ans + 1;
	}
	if(center2 != -1 && center3 != -1) {
		long long center1 = (center2 - center3 + 5000) % 5000;
		long long ans = center1 * 5000 + center2;
		return ans + 1;
	}
	assert(false);
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1328 KB	Correct.
2	Correct	2 ms	1328 KB	Correct.
3	Correct	2 ms	1328 KB	Correct.
4	Correct	2 ms	1336 KB	Correct.
5	Correct	2 ms	1324 KB	Correct.
6	Correct	2 ms	1328 KB	Correct.
7	Correct	2 ms	1328 KB	Correct.
8	Correct	2 ms	1336 KB	Correct.
9	Correct	2 ms	1328 KB	Correct.
10	Correct	2 ms	1328 KB	Correct.
11	Correct	2 ms	1328 KB	Correct.
12	Correct	2 ms	1324 KB	Correct.

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1328 KB	Correct.
2	Correct	2 ms	1328 KB	Correct.
3	Correct	2 ms	1328 KB	Correct.
4	Correct	2 ms	1336 KB	Correct.
5	Correct	2 ms	1324 KB	Correct.
6	Correct	2 ms	1328 KB	Correct.
7	Correct	2 ms	1328 KB	Correct.
8	Correct	2 ms	1336 KB	Correct.
9	Correct	2 ms	1328 KB	Correct.
10	Correct	2 ms	1328 KB	Correct.
11	Correct	2 ms	1328 KB	Correct.
12	Correct	2 ms	1324 KB	Correct.
13	Correct	2 ms	1332 KB	Correct.
14	Correct	2 ms	1508 KB	Correct.
15	Correct	2 ms	1332 KB	Correct.
16	Correct	1 ms	1344 KB	Correct.
17	Correct	1 ms	1332 KB	Correct.
18	Correct	2 ms	1332 KB	Correct.
19	Correct	2 ms	1332 KB	Correct.
20	Correct	2 ms	1332 KB	Correct.
21	Correct	2 ms	1332 KB	Correct.
22	Correct	2 ms	1332 KB	Correct.
23	Correct	2 ms	1348 KB	Correct.
24	Correct	2 ms	1332 KB	Correct.

Subtask #3

0.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1328 KB	Correct.
2	Correct	2 ms	1328 KB	Correct.
3	Correct	2 ms	1328 KB	Correct.
4	Correct	2 ms	1336 KB	Correct.
5	Correct	2 ms	1324 KB	Correct.
6	Correct	2 ms	1328 KB	Correct.
7	Correct	2 ms	1328 KB	Correct.
8	Correct	2 ms	1336 KB	Correct.
9	Correct	2 ms	1328 KB	Correct.
10	Correct	2 ms	1328 KB	Correct.
11	Correct	2 ms	1328 KB	Correct.
12	Correct	2 ms	1324 KB	Correct.
13	Correct	2 ms	1332 KB	Correct.
14	Correct	2 ms	1508 KB	Correct.
15	Correct	2 ms	1332 KB	Correct.
16	Correct	1 ms	1344 KB	Correct.
17	Correct	1 ms	1332 KB	Correct.
18	Correct	2 ms	1332 KB	Correct.
19	Correct	2 ms	1332 KB	Correct.
20	Correct	2 ms	1332 KB	Correct.
21	Correct	2 ms	1332 KB	Correct.
22	Correct	2 ms	1332 KB	Correct.
23	Correct	2 ms	1348 KB	Correct.
24	Correct	2 ms	1332 KB	Correct.
25	Runtime error	1 ms	600 KB	Execution killed with signal 11
26	Halted	0 ms	0 KB	-