Submission #1242894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242894		PenguinsAreCute	Memory 2 (JOI16_memory2)	C++17	100 / 100	0 ms	328 KiB

memory2

#include "Memory2_lib.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(69);
void solve(vector<int> nos, vector<int> idx) {
	int n = idx.size() / 2;
	if(n == 1) {
		Answer(idx[0], idx[1], nos[0]);
		return;
	}
	int x = rng() % (2 * n - 2);
	int y = rng() % (2 * n - 2);
	int z = rng() % (2 * n - 2);
	if(x > y)
		swap(x, y);
	if(y > z)
		swap(y, z);
	if(x > y)
		swap(x, y);
	y++; z+=2;
	int xy = Flip(idx[x], idx[y]);
	int xz = Flip(idx[x], idx[z]);
	int yz = Flip(idx[y], idx[z]);
	int rnd;
	if(xy == xz)
		rnd = y;
	else
		rnd = x;
	int res[2 * n];
	for(int i=0;i<2*n;i++)
		if(i != rnd)
			res[i] = lower_bound(nos.begin(),nos.end(),Flip(idx[i], idx[rnd]))-nos.begin();
	res[rnd] = -1e9;
	int freq[n];
	memset(freq,0,sizeof(freq));
	for(int i=0;i<2*n;i++)
		if(i!=rnd)
			freq[res[i]]++;
	int mn = 0;
	for(int i=0;i<n;i++)
		if(freq[i] & 1)
			mn = i;
	vector<int> nwno, nwpos;
	int ans[n];
	memset(ans,-1,sizeof(ans));
	for(int i=0;i<2*n;i++) {
		if(i==rnd || res[i]==mn)
			nwpos.push_back(idx[i]);
		else if(ans[res[i]] == -1)
			ans[res[i]] = idx[i];
		else
			Answer(idx[i], ans[res[i]], nos[res[i]]);
	}
	for(int i=0;i<n;i++)
		if(ans[i] == -1)
			nwno.push_back(nos[i]);
	solve(nwno, nwpos);
}
void Solve(int T, int N){
	vector<int> v(2*N), u(N);
	iota(v.begin(),v.end(),0);
	iota(u.begin(),u.end(),0);
	solve(u, v);
}

• Subtask 1: 10 / 10
• Subtask 2: 50 / 50
• Subtask 3: 40 / 40