Submission #783214

#TimeUsernameProblemLanguageResultExecution timeMemory
783214APROHACKMechanical Doll (IOI18_doll)C++17
53 / 100
101 ms18504 KiB
#include <bits/stdc++.h> #include "doll.h" #define ll long long #define pb push_back #define ff first #define ss second using namespace std; int n; int currentSwitch = 1; vector<int>goes[100002]; vector<int>c, x, y; vector<ll>potencias2; bool isPot(ll k){ while(k > 1){ if(k % 2 == 1)return false; k/=2; } return true; } int principio, puntero; int generar(ll vec, ll desde, ll cada, ll cuantosHay, bool up){ //cout << "generando " << vec << " desde " << desde << " " << cada << "hay " << cuantosHay << endl; ll tam = goes[vec].size()-desde; ll cuantosReal = (tam + cada-1)/cada; if(cuantosReal == 1 and cuantosHay == 1){ return goes[vec][desde]; } if(cuantosReal <= 0 and cuantosHay == 1){ if(!up){ return principio; }else{ return INT_MAX; } } x.pb(0); y.pb(0); int estoy = currentSwitch ++ ; // 1 x[estoy-1] = generar(vec, desde, cada * 2, cuantosHay/2, false); y[estoy-1] = generar(vec, desde + cada, cada*2, cuantosHay/2, up); if(y[estoy-1] == INT_MAX)puntero = estoy-1; return (-estoy); } void create_circuit(int M, std::vector<int> A) { n = A.size(); for(int i = 1 ; i < n ; i ++){ goes[A[i-1]].pb(A[i]); } int temp = 1; while(temp < 2000000){ potencias2.pb(temp); temp*= 2; } int ultimo = A.back(); //goes[A.back()].pb(0); bool vis[M+1]; memset(vis,false, sizeof vis); c.pb(A[0]); vector<pair<int, int> > toRepair; // switch inicio, indice Y final for(int i = 1 ; i <= M ; i ++)c.pb(0); for(int i = 0 ; i < n ; i ++){ if(A[i] == ultimo)continue; if(!vis[A[i]]){ vis[A[i]] = true; principio = -currentSwitch; ll nextPot = 1; while(nextPot < goes[A[i]].size())nextPot*=2; c[A[i]] = generar(A[i], 0, 1, nextPot, true); if(!isPot(goes[A[i]].size())){ toRepair.pb({c[A[i]], puntero}); //cout << "ins " << c[A[i]] << " " << puntero << endl; } } } if(goes[ultimo].size() == 0){ if(toRepair.size() == 0){ c[ultimo] = 0; answer(c, x, y); return ; }else{ c[ultimo] = toRepair.back().ff; } }else{ principio = -currentSwitch; int nextPot = 1; while(nextPot < goes[ultimo].size())nextPot*=2; if(nextPot == goes[ultimo].size()){ c[ultimo] = generar(ultimo, 0, 1, nextPot*2, true); toRepair.pb({c[ultimo], puntero}); }else { c[ultimo] = generar(ultimo, 0, 1, nextPot, true); toRepair.pb({c[ultimo], puntero}); } } for(int i = toRepair.size() -1 ; i > 0 ; i --){ //cout << "end " << toRepair[i].ss << " to " << toRepair[i-1].ff << endl; y[toRepair[i].ss] = toRepair[i-1].ff; } y[toRepair[0].ss] = 0; answer(c, x, y); }

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:70:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    while(nextPot < goes[A[i]].size())nextPot*=2;
      |          ~~~~~~~~^~~~~~~~~~~~~~~~~~~
doll.cpp:89:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   while(nextPot < goes[ultimo].size())nextPot*=2;
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
doll.cpp:90:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   if(nextPot == goes[ultimo].size()){
      |      ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...