Submission #203440

#TimeUsernameProblemLanguageResultExecution timeMemory
203440theStaticMindMinerals (JOI19_minerals)C++14
85 / 100
215 ms6352 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() #define INF 1000000000//00000000 #define modulo 1000000007 #define mod 998244353 //#define int long long int using namespace std; #include "minerals.h" int last = 0; unordered_set<int> S; void add(int x){ if(S.count(x))S.erase(x); else S.insert(x); } void extract(vector<int>& A, vector<int>& B, vector<int>& X, vector<int>& Y){ int n = sz(A), m = sz(B); int b = 0; random_shuffle(all(B)); random_shuffle(all(B)); for(int i = 0; i < m; i++){ int v; if(b == sz(A)) v = INF; else v = Query(B[i]), add(B[i]); if(v == last){ X.pb(B[i]); b++; } else Y.pb(B[i]); if(v != INF) last = v; } } void divide(vector<int>& A, vector<int>& B){ int n = A.size(); if(n == 1){ Answer(A[0], B[0]); return; } random_shuffle(all(B)); random_shuffle(all(B)); vector<int> X, Y; vector<int> tempA, tempB; for(int i = 0; i <= 0.3 * n; i++)tempA.pb(A[i]); for(int i = 0.3 * n + 1; i < n; i++)tempB.pb(A[i]); if(!(S.count(tempA[0]) ^ S.count(tempB[0]))){ if(tempB.size() > tempA.size()) swap(tempA, tempB); for(int i = 0; i < tempB.size(); i++) last = Query(tempB[i]), add(tempB[i]); } if(S.count(tempB[0])){ swap(tempA, tempB); } extract(tempA, B, X, Y); divide(tempA, X); divide(tempB, Y); } void Solve(int N) { vector<int> A, B; vector<int> arr; for(int i = 1; i <= 2 * N; i++)arr.pb(i); srand(time(NULL)); random_shuffle(all(arr)); random_shuffle(all(arr)); for(auto i : arr){ int q; if(last == N) q = last; else q = Query(i); S.insert(i); if(last == q){ B.pb(i); } else{ A.pb(i); } last = q; } divide(A, B); }

Compilation message (stderr)

minerals.cpp: In function 'void extract(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
minerals.cpp:24:11: warning: unused variable 'n' [-Wunused-variable]
       int n = sz(A), m = sz(B);
           ^
minerals.cpp: In function 'void divide(std::vector<int>&, std::vector<int>&)':
minerals.cpp:56:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < tempB.size(); i++) last = Query(tempB[i]), add(tempB[i]);
                            ~~^~~~~~~~~~~~~~
#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...