| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 122897 | 2019-06-29T13:41:06 Z | Gustav | 도서관 (JOI18_library) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 998244353;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())
int n;
vi found(1010);
/*
int Query(const std::vector<int>& M){
cout << "Query: ";
for(int i = 0; i < sz(M); i++) cout << M[i] << " ";
cout << endl;
int r;
cin >> r;
return r;
}
void Answer(const std::vector<int>& res)
{
cout << "Answer: ";
for(int i = 0; i < sz(res); i++) cout << res[i] << " ";
cout << endl;
}
*/
int endcount(vi o){
vi m(n);
for(int i = 0; i < sz(o); i++){
m[o[i]] = 1;
}
int r1 = Query(m);
for(int i = 0; i < n; i++){
if(m[i]) m[i] = 0;
else if(!found[i]) m[i] = 1;
}
int r2 = Query(m);
if(r1 == r2) return 1;
if(r1+1 == r2) return 0;
if(r1 == r2+1) return 2;
assert(false);
return -1;
}
int find(){
vi left;
for(int i = 0; i < n; i++){
if(!found[i]) left.push_back(i);
}
int lo = 0, hi = sz(left);
while(lo+1 < hi){
cout << lo << " " << hi << endl;
int mid = (lo+hi)/2;
vi c;
for(int i = 0; i < mid; i++){
c.push_back(left[i]);
}
int r = endcount(c);
if(r == 0) lo = mid;
else hi = mid;
}
return left[lo];
}
void Solve(int N){
n = N;
vi start;
vi end;
start.push_back(find());
found[start[0]] = 1;
for(int i = 0; i < n-1; i++){
int r = find();
found[r] = 1;
vi t(n);
t[r] = 1;
t[start[sz(start)-1]] = 1;
if(Query(t) == 1) start.push_back(r);
else end.push_back(r);
}
for(int i = sz(end)-1; i >= 0; i--){
start.push_back(end[i]);
}
for(int i = 0; i < sz(start); i++) start[i]--;
Answer(start);
}
int main(){
cin.sync_with_stdio(false);
cin.tie(0);
Solve(5);
}