Submission #311264

#TimeUsernameProblemLanguageResultExecution timeMemory
311264LucaDantasLibrary (JOI18_library)C++17
0 / 100
47 ms384 KiB
#include <cstdio> #include <vector> #include <cassert> #include<algorithm> #include "library.h" using namespace std; #define pb push_back #define sz(a) (int)((a).size()) vector<vector<int>> grp; void Solve(int n) { // int A = Query(M); // Answer(res); for(int i = 0; i < n; i++) grp.pb({i}); while(sz(grp) > 1) { // puts("OPA"); vector<vector<int>> dir, esq; vector<vector<int>> grande = grp; do { esq.clear(); dir.clear(); vector<int> qr(n); for(int i = 0; i < sz(grande)/2; i++) esq.pb(grande[i]); for(int i = sz(grande)/2; i < sz(grande); i++) dir.pb(grande[i]); for(auto x : esq) for(auto y : x) qr[y] = 1; // puts("ANIMAL"); if(Query(qr) < sz(esq)) {/*puts("a"), */grande = esq; /*printf("%d\n", sz(esq));*/} else { // puts("b"); fill(qr.begin(), qr.end(), 0); for(auto x : dir) for(auto y : x) qr[y] = 1; if(Query(qr) < sz(dir)) {grande = dir/*, puts("x")*/;} else { // puts("y"); while(sz(esq) + sz(dir) > 2) { vector<vector<int>> l1, l2, r1, r2; for(int i = 0; i < sz(dir)/2; i++) r1.pb(dir[i]); for(int i = sz(dir)/2; i < sz(dir); i++) r2.pb(dir[i]); for(int i = 0; i < sz(esq)/2; i++) l1.pb(esq[i]); for(int i = sz(esq)/2; i < sz(esq); i++) l2.pb(esq[i]); fill(qr.begin(), qr.end(), 0); for(auto x : esq) for(auto y : x) qr[y] = 1; for(auto x : r1) for(auto y : x) qr[y] = 1; if(Query(qr) < sz(esq) + sz(r1)) dir = r1; else dir = r2; fill(qr.begin(), qr.end(), 0); for(auto x : l1) for(auto y : x) qr[y] = 1; for(auto x : dir) for(auto y : x) qr[y] = 1; if(Query(qr) < sz(l1) + sz(dir)) esq = l1; else esq = l2; } // break; } } } while(sz(esq) + sz(dir) > 2); // printf("%d %d\n", sz(esq), sz(dir)); // printf("%d %d\n", esq[0][0], dir[0][0]); assert(sz(dir) == 1 && sz(esq) == 1); auto find = [&](vector<int>& achar) { for(int i = 0; i < sz(grp); i++) { if(grp[i].front() == achar.front()) return i; } assert(0); return -1; }; auto apagar = [&](int pos) { swap(grp.back(), grp[pos]); grp.pop_back(); }; if(sz(esq[0]) == 1) swap(esq, dir); vector<int> qr(n); qr[esq[0].back()] = 1; qr[dir[0].front()] = 1; if(Query(qr) == 2) swap(esq, dir); apagar(find(dir[0])); int id = find(esq[0]); for(auto add : dir[0]) grp[id].pb(add); // printf("%d\n", sz(grp)); // for(auto x : grp) { // for(auto y : x) // printf("%d ", y); // printf("\n"); // } // printf("\n"); } for(int i = 0; i < n; i++) grp[0][i]++; Answer(grp[0]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...