oj.uz

Submission #957335

# Submission time Handle Problem Language Result Execution time Memory
957335 2024-04-03T14:00:29 Z parlimoos Library (JOI18_library) C++14
0 / 100
 133 ms 596 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 bs(int v){
    int l = 0 , r = n - 2;
    r -= int(a[v][0] != -1) + int(a[v][1] != -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 = Query(pss);
        pss[v] = 1;
        int d2 = Query(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 = Query(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;
	if(n == 1){
		int d = Query({1});
		Answer({1});
		return;
	}
    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); 
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:71:7: warning: unused variable 'd' [-Wunused-variable]
   71 |   int d = Query({1});
      |       ^

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 344 KB # of queries: 3163
2 Correct 28 ms 344 KB # of queries: 3136
3 Correct 28 ms 344 KB # of queries: 3295
4 Correct 24 ms 344 KB # of queries: 3315
5 Correct 35 ms 596 KB # of queries: 3303
6 Correct 26 ms 340 KB # of queries: 3307
7 Correct 29 ms 344 KB # of queries: 3303
8 Correct 26 ms 344 KB # of queries: 3160
9 Correct 34 ms 344 KB # of queries: 3278
10 Correct 16 ms 344 KB # of queries: 1950
11 Correct 0 ms 344 KB # of queries: 1
12 Runtime error 133 ms 416 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 344 KB # of queries: 3163
2 Correct 28 ms 344 KB # of queries: 3136
3 Correct 28 ms 344 KB # of queries: 3295
4 Correct 24 ms 344 KB # of queries: 3315
5 Correct 35 ms 596 KB # of queries: 3303
6 Correct 26 ms 340 KB # of queries: 3307
7 Correct 29 ms 344 KB # of queries: 3303
8 Correct 26 ms 344 KB # of queries: 3160
9 Correct 34 ms 344 KB # of queries: 3278
10 Correct 16 ms 344 KB # of queries: 1950
11 Correct 0 ms 344 KB # of queries: 1
12 Runtime error 133 ms 416 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -