Submission #1052801

#TimeUsernameProblemLanguageResultExecution timeMemory
1052801HunterXDLibrary (JOI18_library)C++17
0 / 100
10 ms444 KiB
#include <bits/stdc++.h> #include "library.h" using namespace std; #define f first #define s second #define pb push_back mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; vector<deque<int>> piles; vector<int> pile_range(int l, int r){ vector<int> res(n, 0); for(int i = l; i <= r; i++){ for(auto v: piles[i]) res[v-1] = 1; } return res; } int query_range(int l, int r, int el){ vector<int> check = pile_range(l, r); check[el-1] = 1; return Query(check); } void merge1(int l, int r, int el){ // 11 queries at most int il = l, ir = r; while(ir-il+1 > 1){ int mid = (il + ir) / 2; int q = query_range(il, mid, el); if(q == mid-il+1) ir = mid; else il = mid+1; } vector<int> check(n, 0); check[el-1] = 1, check[piles[il].front()-1] = 1; int q = Query(check); if(q == 1) piles[il].push_front(el); else piles[il].push_back(el); } void merge2(int l, int r, int el){ // 22 queries at most int il = l, ir = r; if(ir < il) return; for(int i = 9; i >= 0; i--){ int im = il + (1 << i); if(im >= ir) continue; int q = query_range(im, ir, el); if(q == ir-im) il = im; } for(int i = 9; i >= 0; i--){ int im = ir - (1 << i); if(im <= il) continue; int q = query_range(il, im, el); if(q == im-il) ir = im; } bool il_front = false, ir_front = false; vector<int> check(n, 0); check[el-1] = 1, check[piles[il].front()-1] = 1; int q = Query(check); if(q == 1) il_front = true; check = vector<int>(n, 0); check[el-1] = 1, check[piles[ir].front()-1] = 1; q = Query(check); if(q == 1) ir_front = true; if(il_front && ir_front){ piles[il].push_front(el); while(!piles[ir].empty()){ piles[il].push_front(piles[ir].front()); piles[ir].pop_front(); } } if(il_front && !ir_front){ piles[il].push_front(el); while(!piles[ir].empty()){ piles[il].push_front(piles[ir].back()); piles[ir].pop_back(); } } if(!il_front && ir_front){ piles[il].push_back(el); while(!piles[ir].empty()){ piles[il].push_back(piles[ir].front()); piles[ir].pop_front(); } } if(!il_front && !ir_front){ piles[il].push_back(el); while(!piles[ir].empty()){ piles[il].push_back(piles[ir].back()); piles[ir].pop_back(); } } piles.erase(piles.begin() + ir); } void Solve(int N){ n = N; vector<int> elements(N), res(N); iota(elements.begin(), elements.end(), 1); // shuffle(elements.begin(), elements.end(), rng); piles.pb({elements[0]}); for(int i = 1; i < N; i++){ int el = elements[i], q, m; q = query_range(0, piles.size()-1, el); if(q == piles.size()+1){ piles.pb({el}); continue; } if(q == piles.size()) merge1(0, piles.size()-1, el); if(q == piles.size()-1) merge2(0, piles.size()-1, el); // cout << "Piles: " << endl; // for(auto v: piles){ // for(auto u: v){ // cout << u << " "; // } // cout << endl; // } } res.clear(); for(auto v: piles){ while(!v.empty()){ res.pb(v.front()); v.pop_front(); } } for(auto v: res){ cout << v << " "; } Answer(res); }

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:131:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   if(q == piles.size()+1){
      |      ~~^~~~~~~~~~~~~~~~~
library.cpp:136:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   if(q == piles.size()) merge1(0, piles.size()-1, el);
      |      ~~^~~~~~~~~~~~~~~
library.cpp:137:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::deque<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   if(q == piles.size()-1) merge2(0, piles.size()-1, el);
      |      ~~^~~~~~~~~~~~~~~~~
library.cpp:127:28: warning: unused variable 'm' [-Wunused-variable]
  127 |   int el = elements[i], q, m;
      |                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...