Submission #957333

#	Time	Username	Problem	Language	Result	Execution time	Memory
957333		parlimoos	Library (JOI18_library)	C++14	0 / 100	146 ms	600 KiB

library

//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;
    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: 0 / 19
• Subtask 2: 0 / 81