Submission #540747

#TimeUsernameProblemLanguageResultExecution timeMemory
540747AugustinasJucasICC (CEOI16_icc)C++14
61 / 100
165 ms612 KiB
#include <bits/stdc++.h> #include "icc.h" using namespace std; int n; vector<vector<int> > comp; pair<vector<int>, vector<int> > randomPuse(int sz) { vector<int> vec (sz); for(int i = 0; i < vec.size(); i++) vec[i] = i; shuffle(vec.begin(), vec.end(), default_random_engine(rand())); vector<int> a, b; for(int i = 0; i < sz/2; i++) a.push_back(vec[i]); for(int i = sz/2; i < sz; i++) b.push_back(vec[i]); return {a, b}; } vector<int> sudek(vector<int> &a) { vector<int> ret; for(auto &x : a) for(auto &y : comp[x]) ret.push_back(y); return ret; } int mas1[101], mas2[102]; bool quer(vector<int> &a, vector<int> &b) { for(int i = 0; i < a.size(); i++) mas1[i] = a[i]; for(int i = 0; i < b.size(); i++) mas2[i] = b[i]; int ret = query(a.size(), b.size(), mas1, mas2); // cout << "quer(["; for(auto x : a) cout << x << " "; cout << "], ["; for(auto x : b) cout << x << " "; cout << "]) = " << ret << endl; return ret; } pair<vector<int>, vector<int> > raskPriesingus() { while(true) { auto pr = randomPuse(comp.size()); auto a = pr.first; auto b = pr.second; auto A1 = sudek(a); auto B1 = sudek(b); if(quer(A1, B1) == 1) { return {A1, B1}; } } return {{-1}, {-1}}; } vector<int> sudek(vector<int> &a, int kek) { vector<int> ret = a; ret.resize(kek); return ret; } int dvej(vector<int> &a, vector<int> &b) { int l = 0; int r = b.size(); int ans = -1; int mid; while(l <= r) { mid = (l + r) / 2; auto sud = sudek(b, mid); if(quer(a, sud) == 0) { l = mid+1; ans = max(ans, mid); }else { r = mid-1; } } return b[ans]; } void renewComp(int a, int b) { int i1 = -1; int i2 = -1; for(int i = 0; i < comp.size(); i++) { bool is = 0; for(auto &x : comp[i]) if(x == a || x == b) is = 1; if(is) { if(i1 == -1) i1 = i; else i2 = i; } } for(auto &x : comp[i1]) comp[i2].push_back(x); comp.erase(comp.begin() + i1); } void raskBriauna(){ auto pries = raskPriesingus(); auto a = pries.first; auto b = pries.second; /* cout << "gaunu, kad priesingose pusese yra: ["; for(auto x : a) cout << x << " "; cout << "] ir ["; for(auto x : b) cout << x << " "; cout << "]\n\n";*/ // tik viena pora yra tarp a ir b int A = dvej(a, b); int B = dvej(b, a); setRoad(A, B); renewComp(A, B); } void run(int N) { srand(time(0)); n = N; for(int i = 1; i <= n; i++) comp.push_back({i}); for(int i = 0; i < n-1; i++) { raskBriauna(); } }

Compilation message (stderr)

icc.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > randomPuse(int)':
icc.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < vec.size(); i++) vec[i] = i;
      |                    ~~^~~~~~~~~~~~
icc.cpp: In function 'bool quer(std::vector<int>&, std::vector<int>&)':
icc.cpp:27:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0; i < a.size(); i++) mas1[i] = a[i];
      |                    ~~^~~~~~~~~~
icc.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i < b.size(); i++) mas2[i] = b[i];
      |                    ~~^~~~~~~~~~
icc.cpp: In function 'void renewComp(int, int)':
icc.cpp:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0; i < comp.size(); 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...