Submission #961167

#TimeUsernameProblemLanguageResultExecution timeMemory
961167steveonalexLibrary (JOI18_library)C++17
100 / 100
185 ms1532 KiB
#include <bits/stdc++.h> #include "library.h" using namespace std; typedef long long ll; typedef unsigned long long ull; #define ALL(v) (v).begin(), (v).end() #define MASK(i) (1LL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) // mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); mt19937_64 rng(1); ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;} ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll LASTBIT(ll mask){return mask & (-mask);} ll pop_cnt(ll mask){return __builtin_popcountll(mask);} ll ctz(ll mask){return __builtin_ctzll(mask);} ll clz(ll mask){return __builtin_clzll(mask);} ll logOf(ll mask){return 63 - clz(mask);} template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b){a = b; return true;} return false; } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b){a = b; return true;} return false; } template <class T> void printArr(T& a, string separator = " ", string finish = "\n"){ for(auto i: a) cout << i << separator; cout << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } // namespace Interactor{ // int n; // vector<int> perm, pos, ans; // int Query(vector<bool> a){ // // cout << "? "; printArr(a); // vector<bool> ligma(n+2); // for(int i=0; i<n; ++i) ligma[pos[i]] = a[i]; // int cnt = 0; // for(int i = 0; i<=n; ++i) if (ligma[i] == 0 && ligma[i+1] == 1) cnt++; // // cout << "-> " << cnt << "\n"; // return cnt; // } // void Answer(vector<int> a){ // ans = a; // } void merge_arr(vector<int> &a, vector<int> b){ for(int i: b) a.push_back(i); } void Solve(int n){ vector<vector<int>> sigma(n); for(int i = 0; i<n; ++i) sigma[i].push_back(i); for(int i = n-1; i>=0; --i){ int iteration = 2; while(iteration--){ int l = i + 1, r = sigma.size(); while(l < r){ int mid = (l + r) >> 1; vector<int> S = sigma[i]; for(int j = i+1; j<=mid; ++j) merge_arr(S, sigma[j]); vector<int> card(n); for(int j: S) card[j] = true; if (Query(card) < mid - i + 1) r = mid; else l = mid + 1; } if (l == sigma.size()) break; bool found = false; for(int x = 0; x <= 1; ++x) for(int y = 0; y<=1; ++y) if (!found) { vector<int> card(n); if (x == 0) card[sigma[i][0]] = 1; else card[sigma[i].back()] = 1; if (y == 0) card[sigma[l][0]] = 1; else card[sigma[l].back()] = 1; if (Query(card) == 1){ if (!x) reverse(ALL(sigma[i])); if (y) reverse(ALL(sigma[l])); found = true; break; } } merge_arr(sigma[i], sigma[l]); sigma.erase(sigma.begin() + l); } } vector<int> ans = sigma[0]; if (ans.size() != n) exit(1); for(int &i: ans) i++; Answer(ans); } // bool solve(int _n){ // n = _n; // perm.resize(n); ans.clear(); // for(int i = 0; i<n; ++i) perm[i] = i + 1; // shuffle(ALL(perm), rng); // pos.resize(n); // for(int i = 0; i<n; ++i) pos[perm[i]-1] = i+1; // Solve(n); // if (ans != perm) reverse(ALL(ans)); // return ans == perm; // } // } // int main(void){ // ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // int n = 5; // bool verdict = Interactor::solve(n); // if (verdict) cout << "AC\n"; // else cout << "WA\n"; // return 0; // }

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                 if (l == sigma.size()) break;
      |                     ~~^~~~~~~~~~~~~~~
library.cpp:112:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |         if (ans.size() != n) exit(1);
      |             ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...