| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 961165 | steveonalex | Library (JOI18_library) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
printArr(perm);
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<bool> 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<bool> 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;
// }