Submission #1242037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242037		salmon	Memory 2 (JOI16_memory2)	C++20	100 / 100	1 ms	328 KiB

memory2

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


void Solve(int T, int N){
	if(T == 500) return;
		
	int name[N * 2 + 5];
	
	for(int i = 0; i < N * 2; i++) name[i] = -1;
		
	vector<int> proc = {0,1,2,3};
	if(N == 1){
		proc.pop_back();
		proc.pop_back();
	}
	
	int cont = 4;
	bool pastd = false;
	
	while(proc.size() == 4){
		if(pastd){
			set<int> de[4];	
			
			for(int j = 0; j < 3; j++){
				int num = Flip(proc[j],proc[3]);
				
				de[j].insert(num);
				de[3].insert(num);
			}
			
			if(de[3].size() == 1){
				name[proc[3]] = *de[3].begin();
				proc[3] = -1;
			}
			else{
				if(*de[1].begin() != *de[0].begin()){
					swap(de[1],de[2]);
					swap(proc[1],proc[2]);
				}
				if(*de[1].begin() != *de[0].begin()){
					swap(de[0],de[2]);
					swap(proc[0],proc[2]);
				}
				
				name[proc[0]] = *de[0].begin();
				proc[0] = -1;
				name[proc[1]] = *de[1].begin();
				proc[1] = -1;
				
				pastd = false;
			}
		}
		else{
			set<int> de[4];	
			
			for(int j = 0; j < 4; j++){
				for(int k = j + 1; k < 4; k++){
					int num = Flip(proc[j],proc[k]);
					
					de[j].insert(num);
					de[k].insert(num);
				}
			}
			
			vector<pair<int,int>> v(0);
			
			for(int i = 0; i < 4; i++) v.push_back({de[i].size(), i});
			
			sort(v.begin(),v.end());
			
			/*for(pair<int,int> ii : v) printf("%d ",ii.first);
			printf("\n");*/
			
			if(v[3].first == 3){
				name[proc[v[0].second]] = *de[v[0].second].begin();
				proc[v[0].second] = -1;
				
				de[v[1].second].erase(*de[v[0].second].begin());
				name[proc[v[1].second]] = *de[v[1].second].begin();
				proc[v[1].second] = -1;
			}
			else if(v[1].first == 1){
				name[proc[v[0].second]] = *de[v[0].second].begin();
				proc[v[0].second] = -1;
				
				name[proc[v[1].second]] = *de[v[1].second].begin();
				proc[v[1].second] = -1;
			}
			else{
				name[proc[v[0].second]] = *de[v[0].second].begin();
				proc[v[0].second] = -1;
				
				pastd = true;
			}
		}
		
		vector<int> temp = proc;
		proc.clear();
		
		for(int i : temp) if(i != -1) proc.push_back(i);
		
		for(int i = 0; i < 2; i++){
			if(proc.size() != 4 && cont != N * 2){
				proc.push_back(cont);
				cont++;
			}
		}
		
		//for(int i = 0; i < N * 2; i++) printf("%d ",name[i]);
		//printf("\n");
	}
	
	vector<int> visited[N];
	
	for(int i = 0; i < N; i++) visited[i].clear();
	
	for(int i = 0; i < N * 2; i++){
		if(name[i] != -1) visited[name[i]].push_back(i);
	}
	
	if(proc.size() != 2){
		set<int> de[3];	
			
		for(int j = 0; j < 3; j++){
			for(int k = j + 1; k < 3; k++){
				int num = Flip(proc[j],proc[k]);
				
				de[j].insert(num);
				de[k].insert(num);
			}
		}
		
		vector<pair<int,int>> v(0);
		
		for(int i = 0; i < 3; i++) v.push_back({de[i].size(), i});
		
		sort(v.begin(),v.end());
		
		name[proc[v[0].second]] = *de[v[0].second].begin();
		visited[name[proc[v[0].second]]].push_back(proc[v[0].second]); 
	}
	
	for(int i = 0; i < N; i++){
		if(visited[i].empty()){
			for(int j = 0; j < N * 2; j++){
				if(name[j] == -1) visited[i].push_back(j);
			}
		}
	}
	
	for(int i = 0; i < N; i++){
		Answer(visited[i][0],visited[i][1],i);
	}
	
	return;
}
/*
1 1 1000
0
0 0

1 4 1000
2 3 0 1
0 0 1 2 3 2 1 3

1 4 1000
0 3 1 2
0 1 2 2 3 3 0 1
 */

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