Submission #991715

#	Time	Username	Problem	Language	Result	Execution time	Memory
991715		aryan12	Magic Show (APIO24_show)	C++17	5 / 100	2 ms	1340 KiB

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 / 5000;
    long long center2 = x % 5000;
    long long center3 = (center2 - center1 + 5000) % 5000;
    vector<pair<int, int> > edges;
    for(long long i = 0; i < 1667; i++) {
    	if(center1 != i) {
    		edges.push_back({center1 + 1, i + 1});
    		unite(i, center1);
    	}
    }
    for(long long i = 1667; i < 3334; i++) {
    	if(center2 != i) {
    		edges.push_back({center2 + 1, i + 1});
    		unite(i, center2);
    	}
    }
    for(long long i = 3334; i < 5000; i++) {
    	if(center3 != 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;
	}
	if(center1 != -1 && center3 != -1) {
		long long center2 = (center1 + center3) % 5000;
		long long ans = center1 * 5000 + center2;
		return ans;
	}
	if(center2 != -1 && center3 != -1) {
		long long center1 = (center2 - center3 + 5000) % 5000;
		long long ans = center1 * 5000 + center2;
		return ans;
	}
	assert(false);
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65