Submission #122899

#	Time	Username	Problem	Language	Result	Execution time	Memory
122899		Gustav	Library (JOI18_library)	C++14	0 / 100	237 ms	404 KiB

library

#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);
}
*/

• Subtask 1: 0 / 19
• Subtask 2: 0 / 81