Submission #1242008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242008		PenguinsAreCute	Memory 2 (JOI16_memory2)	C++17	60 / 100	1 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 rnd = rng() % (2 * n);
	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: 0 / 40