Submission #1022576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022576		manizare	Library (JOI18_library)	C++14	100 / 100	202 ms	1044 KiB

library

#include "library.h"
#include <bits/stdc++.h>
 
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double 
#define ll long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2000 + 10  , sq = 550,  inf = 1e8+10 , mod = 10007 , lg = 20  ;
int nx[maxn] , n   , mark[maxn] ;

int que(){
    vector <int> vec; 
    rep(i ,1 , n){
        vec.pb(mark[i]) ;
    }
    return Query(vec) ; 
}
void cl(){
    rep(i,1,n)mark[i] =0  ; 
}
vector <int> a[maxn]; 
void add(int x){
    for(int f : a[x])mark[f] = 1; 
}
void upd(int x , int y){
    cl() ;
    a[x].pb(y) ; 
    rep(i ,1 ,sz(a[x])-1)mark[a[x][i]] = 1; 
    if(que() != 1){
        a[x].pop_back() ; 
        reverse(all(a[x])) ;
        a[x].pb(y) ; 
    }
}

int  find(vector<int> vec , int x){
    if(sz(vec) ==1)return vec[0] ; 
    vector <int> f ;
    cl() ;
    int ted= 1 ; 
    rep(i , 0, sz(vec)/2-1){
        add(vec[i]) ; ted += 1 ; 
    }
    mark[x] = 1 ; 
    if(que() == ted){
        vector <int> vec2 ;
        rep(i, sz(vec)/2 , sz(vec)-1){
            vec2.pb(vec[i]) ; 
        }       
        return find(vec2 , x)  ;
    }
    vector <int> vec2 ; 
    rep(i , 0 , sz(vec)/2-1){
        vec2.pb(vec[i]) ; 
    }
    return find(vec2 , x) ;
}

void Solve(int N){
    n = N ; 
    vector <int> m ;
    rep(i ,1 , n){

        m.pb(i) ;
        a[i].pb(i) ; 
        cl() ;
        for(int x : m)add(x);
        if(sz(m) == que()){
            continue ; 
        }
        m.pop_back() ; 
        int v=  find(m , i) ; 
        upd(v , i) ;
        cl() ;
        for(int x : m)add(x) ;
        if(sz(m) == que()){
            continue ; 
        }
        vector <int> v2 ;
        for(int x :  m){
            if(x == v)continue ; 
            v2.pb(x) ; 
        }
        int u = find(v2 , i) ;
        upd(u , i) ;
        a[u].pop_back() ;
        while(sz(a[u])){
            a[v].pb(a[u].back()) ; 
            a[u].pop_back() ;
        }
        v2.clear() ; 
        for(int x : m){
            if(x == u)continue;
            v2.pb(x) ;
        }
        m = v2; 
    }
    Answer(a[m[0]]) ; 
}

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