Submission #477670

#TimeUsernameProblemLanguageResultExecution timeMemory
477670HappyPacManMinerals (JOI19_minerals)C++14
100 / 100
88 ms3028 KiB
#include "minerals.h" #include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int curr = 0; bool change(int u){ int nxt = Query(u); bool res = (nxt != curr); curr = nxt; return res; } void rec(vector<int> &A,vector<int> &B,bool rev){ int len = A.size(); if(len == 1){ Answer(A[0],B[0]); return; } shuffle(A.begin(),A.end(),rng); shuffle(B.begin(),B.end(),rng); int mid = (rev?382:618)*len/1000; if(mid == 0) mid++; if(mid == len) mid--; vector<int> nA[2],nB[2]; for(int i=0;i<len;i++){ if(i < mid) nA[0].push_back(A[i]); else nA[1].push_back(A[i]); if((mid <= i) ^ rev) change(A[i]); } for(int i=0;i<len;i++){ if(nB[0].size() == nA[0].size()) nB[1].push_back(B[i]); else if(nB[1].size() == nA[1].size()) nB[0].push_back(B[i]); else if(change(B[i])) nB[0].push_back(B[i]); else nB[1].push_back(B[i]); } rec(nA[0],nB[0],0); rec(nA[1],nB[1],1); } void Solve(int N){ vector<int> group[2]; for(int i=1;i<=2*N;i++) group[change(i)].push_back(i); rec(group[0],group[1],1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...