oj.uz

Submission #1022576

# Submission time Handle Problem Language Result Execution time Memory
1022576 2024-07-13T18:34:25 Z manizare Library (JOI18_library) C++14
100 / 100
 202 ms 1044 KB 
#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.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 592 KB # of queries: 1436
2 Correct 14 ms 348 KB # of queries: 1440
3 Correct 12 ms 748 KB # of queries: 1503
4 Correct 16 ms 600 KB # of queries: 1508
5 Correct 12 ms 508 KB # of queries: 1508
6 Correct 16 ms 492 KB # of queries: 1500
7 Correct 13 ms 344 KB # of queries: 1511
8 Correct 22 ms 500 KB # of queries: 1434
9 Correct 15 ms 344 KB # of queries: 1500
10 Correct 11 ms 344 KB # of queries: 887
11 Correct 0 ms 344 KB # of queries: 1
12 Correct 0 ms 344 KB # of queries: 4
13 Correct 1 ms 344 KB # of queries: 7
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 61
16 Correct 1 ms 340 KB # of queries: 132

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 592 KB # of queries: 1436
2 Correct 14 ms 348 KB # of queries: 1440
3 Correct 12 ms 748 KB # of queries: 1503
4 Correct 16 ms 600 KB # of queries: 1508
5 Correct 12 ms 508 KB # of queries: 1508
6 Correct 16 ms 492 KB # of queries: 1500
7 Correct 13 ms 344 KB # of queries: 1511
8 Correct 22 ms 500 KB # of queries: 1434
9 Correct 15 ms 344 KB # of queries: 1500
10 Correct 11 ms 344 KB # of queries: 887
11 Correct 0 ms 344 KB # of queries: 1
12 Correct 0 ms 344 KB # of queries: 4
13 Correct 1 ms 344 KB # of queries: 7
14 Correct 0 ms 344 KB # of queries: 10
15 Correct 1 ms 344 KB # of queries: 61
16 Correct 1 ms 340 KB # of queries: 132
17 Correct 194 ms 856 KB # of queries: 9815
18 Correct 184 ms 648 KB # of queries: 9694
19 Correct 202 ms 820 KB # of queries: 9758
20 Correct 176 ms 764 KB # of queries: 9183
21 Correct 158 ms 624 KB # of queries: 8616
22 Correct 189 ms 1040 KB # of queries: 9814
23 Correct 179 ms 344 KB # of queries: 9788
24 Correct 59 ms 516 KB # of queries: 4549
25 Correct 175 ms 1044 KB # of queries: 9589
26 Correct 162 ms 788 KB # of queries: 8981
27 Correct 57 ms 508 KB # of queries: 4525
28 Correct 55 ms 592 KB # of queries: 2998
29 Correct 79 ms 768 KB # of queries: 2995
30 Correct 54 ms 592 KB # of queries: 2998