oj.uz

Submission #957348

# Submission time Handle Problem Language Result Execution time Memory
957348 2024-04-03T14:12:28 Z parlimoos Library (JOI18_library) C++14
100 / 100
 351 ms 344 KB 
//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "library.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , a[2000][2];
vector<int> pss;

int q(vector<int> e){
	if(count(e.bg() , e.end() , 1) == 1) return 1;
	return Query(e);
}
int bs(int v){
    int l = 0 , r = n - 2;
    r -= int(a[v][0] != -1) + int(a[v][1] != -1);
	if(r < l) return -1;
    while(r - l + 1 > 1){
        int c = ((r + l - 1) >> 1) , j = 0;
        for(int i = 0 ; i < n ; i++){
            if(i == v or i == a[v][0] or i == a[v][1]) pss[i] = 0;
            else pss[i] = int(j >= l and j <= c) , j++;
        }

        int d1 = q(pss);
        pss[v] = 1;
        int d2 = q(pss);
        if(d1 + 1 == d2) l = c + 1;
        else r = c;
    }
    for(int i = 0 ; i < n ; i++) pss[i] = 0;
    int j = 0;
    for(int i = 0 ; i < n ; i++){
        if(i == v or i == a[v][0] or i == a[v][1]) continue;
        if(j++ == l){
            l = i;
            break;
        }
    }
    pss[l] = 1 , pss[v] = 1;
    int d = q(pss);
    if(d == 1) return l;
    else return -1;
}
void f(){
	if(n == 1) return;
    int v = 0 , cnt = 0;
    while(true){
        int d = bs(v);
        cnt++;
        if(d == -1) break;
        a[v][1] = d , a[d][0] = v , v = d;
    }
    if(cnt == n) return;
    v = 0;
    while(true){
        int d = bs(v);
        if(d == -1) break;
        a[v][0] = d , a[d][1] = v , v = d;
    }
}
void Solve(int N){
    n = N;
    fill(&a[0][0] , &a[n - 1][2] , -1);
    for(int i = 0 ; i < n ; i++) pss.pb(0);
    f();
    int l = 0;
    while(a[l][0] != -1) l = a[l][0];
    for(int i = 0 ; i < n ; i++ , l = a[l][1]) pss[i] = l + 1;
    Answer(pss); 
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 344 KB # of queries: 2836
2 Correct 23 ms 344 KB # of queries: 2816
3 Correct 27 ms 344 KB # of queries: 2982
4 Correct 29 ms 344 KB # of queries: 2991
5 Correct 33 ms 344 KB # of queries: 2982
6 Correct 26 ms 344 KB # of queries: 2984
7 Correct 32 ms 344 KB # of queries: 2985
8 Correct 24 ms 344 KB # of queries: 2841
9 Correct 29 ms 344 KB # of queries: 2960
10 Correct 12 ms 344 KB # of queries: 1818
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 111
16 Correct 2 ms 344 KB # of queries: 252

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 344 KB # of queries: 2836
2 Correct 23 ms 344 KB # of queries: 2816
3 Correct 27 ms 344 KB # of queries: 2982
4 Correct 29 ms 344 KB # of queries: 2991
5 Correct 33 ms 344 KB # of queries: 2982
6 Correct 26 ms 344 KB # of queries: 2984
7 Correct 32 ms 344 KB # of queries: 2985
8 Correct 24 ms 344 KB # of queries: 2841
9 Correct 29 ms 344 KB # of queries: 2960
10 Correct 12 ms 344 KB # of queries: 1818
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 1
13 Correct 0 ms 344 KB # of queries: 5
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 111
16 Correct 2 ms 344 KB # of queries: 252
17 Correct 325 ms 344 KB # of queries: 19918
18 Correct 324 ms 344 KB # of queries: 19663
19 Correct 332 ms 344 KB # of queries: 19917
20 Correct 318 ms 344 KB # of queries: 18552
21 Correct 278 ms 344 KB # of queries: 17362
22 Correct 341 ms 344 KB # of queries: 19912
23 Correct 351 ms 344 KB # of queries: 19903
24 Correct 110 ms 344 KB # of queries: 9250
25 Correct 331 ms 344 KB # of queries: 19417
26 Correct 291 ms 344 KB # of queries: 18079
27 Correct 114 ms 344 KB # of queries: 9209
28 Correct 318 ms 344 KB # of queries: 19894
29 Correct 317 ms 344 KB # of queries: 19870
30 Correct 316 ms 344 KB # of queries: 19894