Submission #1169900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169900		jaskier	Minerals (JOI19_minerals)	C++20	6 / 100	13 ms	492 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
vector<int> vec, teraz;
vector<pair<int, int>> parki;
bool odznaczone[100000];
void Solve(int n) 
{unsigned long long now$=chrono::duration_cast<chrono::nanoseconds>(chrono::system_clock::now().time_since_epoch()).count();
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(now$);
	for(int i=1; i<=2*n; i++) {
		vec.push_back(i);
	}	
	int podzial, poprz, ziom, nowy, stary;
	while(vec.size()>200) {
		random_shuffle(vec.begin(), vec.end());
		podzial=sqrt(vec.size());
		poprz=-1;
		for(int i=0; i<vec.size(); i++) {
			if(i/podzial != poprz) {
				poprz=i/podzial;
				for(auto xd:teraz) {
					ziom = Query(xd);
				}	
				teraz.clear();
				ziom=Query(vec[i]);
				teraz.push_back(vec[i]);
				continue;
			}	
			nowy=Query(vec[i]);
			if(nowy!=ziom) {
				teraz.push_back(vec[i]);
				ziom=nowy;
			}
			else {
				for(int j=0; j<teraz.size(); j++) {
					if(odznaczone[teraz[j]]) {
						continue;
					}
					stary=nowy;
					nowy=Query(teraz[j]);
					if(nowy==stary) {
						parki.push_back({teraz[j], vec[i]});
						odznaczone[teraz[j]]=1;
						odznaczone[vec[i]]=1;
						for(int d=0; d<=j; d++) {
							nowy=Query(teraz[d]);
						}	
						break;
					}	
				}	
			}	
		}	
		vec.clear();
		for(int i=1; i<=n; i++) {
			if(!odznaczone[i]) {
				vec.push_back(i);
			}
		}	
	}
	
	
	
	random_shuffle(vec.begin(), vec.end());
	ziom=0;
	for(int i=0; i<vec.size(); i++) {
		nowy=Query(vec[i]);
		if(nowy!=ziom) {
			teraz.push_back(vec[i]);
			ziom=nowy;
		}
		else {
			for(int j=0; j<teraz.size(); j++) {
				if(odznaczone[teraz[j]]) {
					continue;
				}
				stary=nowy;
				nowy=Query(teraz[j]);
				if(nowy==stary) {
					parki.push_back({teraz[j], vec[i]});
					odznaczone[teraz[j]]=1;
					odznaczone[vec[i]]=1;
					for(int d=0; d<=j; d++) {
						nowy=Query(teraz[d]);
					}	
					break;
				}	
			}	
		}	
	}	
	
	
	
	for(auto xd:parki) {
		Answer(xd.first, xd.second);
	}
}	

• Subtask 1: 6 / 6
• Subtask 2: 0 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10