Submission #891665

#TimeUsernameProblemLanguageResultExecution timeMemory
891665vjudge1Mechanical Doll (IOI18_doll)C++17
100 / 100
128 ms17472 KiB
#include "doll.h" #include <bits/stdc++.h> using namespace std; using vi = vector<int>; vi X, Y; vector<pair<int, int> > VP; int gen(int niv, int nr) { int id = X.size(); X.push_back(0); Y.push_back(0); //cout << niv << " " << nr << "\n"; if(niv == 1 && nr == 2) { return -id - 1; } else if(niv == 1 && nr == 1) { X[id] = -1; return -id - 1; } if(nr <= (1 << (niv - 1))) { int S = gen(niv - 1, nr); Y[id] = S; X[id] = -1; return -id - 1; } else { Y[id] = gen(niv - 1, (1 << (niv - 1))); X[id] = gen(niv - 1, nr - (1 << (niv - 1))); return -id - 1; } return -id - 1; } void create_circuit(int M, vi A) { A.push_back(0); map<int, int> Fr; int frmax = 0; for(auto it : A) { ++Fr[it]; frmax = max(frmax, Fr[it]); } if(frmax <= 4) { int ult = 0; vector<vi> Urm(M + 1); for(int i = 0; i < A.size(); ++i) { Urm[ult].push_back(A[i]); ult = A[i]; } vi C(M + 1, -1), X, Y; for(int i = 0; i <= M; ++i) { if(Urm[i].empty()) { C[i] = 0; continue; } if(Urm[i].size() == 1) { C[i] = Urm[i][0]; continue; } if(Urm[i].size() == 2) { X.push_back(Urm[i][0]); Y.push_back(Urm[i][1]); C[i] = -X.size(); continue; } if(Urm[i].size() == 3) { int id = X.size(); X.push_back(-id-2); Y.push_back(-id-3); X.push_back(Urm[i][0]); Y.push_back(Urm[i][1]); X.push_back(-id - 1); Y.push_back(Urm[i][2]); C[i] = -id - 1; continue; } if(Urm[i].size() == 4) { int id = X.size(); X.push_back(-id-2); Y.push_back(-id-3); X.push_back(Urm[i][0]); Y.push_back(Urm[i][2]); X.push_back(Urm[i][1]); Y.push_back(Urm[i][3]); C[i] = -id - 1; continue; } assert(0); } // cout << "C: "; // for(auto it : C) // cout << it << " "; // cout << "\n"; // cout << "X: "; // for(auto it : X) // cout << it << " "; // cout << "\n"; // cout << "Y: "; // for(auto it : Y) // cout << it << " "; // cout << "\n"; answer(C, X, Y); } else { int niv = 1; while((1 << niv) <= A.size()) ++niv; gen(niv, A.size()); vi C(M + 1, -1); vi Stare(X.size(), 0); int u = -1, p = 0; ////cout << "ASSIGN\n"; do { if(u > 0) { u = -1; } int id = -u - 1; if(!Stare[id]) { Stare[id] ^= 1; if(X[id]) u = X[id]; else { u = X[id] = A[p++]; } } else { Stare[id] ^= 1; if(Y[id]) u = Y[id]; else { u = Y[id] = A[p++]; } } } while(u != 0); int nr0 = 0; for(auto &it : X) nr0 += !it; for(auto &it : Y) nr0 += !it; //cout << "In total " << nr0 << "\n"; //for(auto it : Stare) //cout << it << " "; //cout << "\n"; //cout << "C: "; //for(auto it : C) //cout << it << " "; //cout << "\n"; //cout << "X: "; //for(auto it : X) //cout << it << " "; //cout << "\n"; //cout << "Y: "; //for(auto it : Y) //cout << it << " "; //cout << "\n"; answer(C, X, Y); } }

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, vi)':
doll.cpp:49:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int i = 0; i < A.size(); ++i) {
      |                        ~~^~~~~~~~~~
doll.cpp:109:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         while((1 << niv) <= A.size()) ++niv;
      |               ~~~~~~~~~~~^~~~~~~~~~~
#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...