Submission #44337

#	Time	Username	Problem	Language	Result	Execution time	Memory
44337		chonka	Library (JOI18_library)	C++14	100 / 100	539 ms	704 KiB

library

#include "library.h"
#include<iostream>
#include<stdio.h>
using namespace std ;

int n ;
vector < int > ret ;

vector < int > aux ;

void rev ( vector < int > &v ) {
    int sz = v.size ( ) ;
    int i ;
    for ( i = 0 ; i < ( sz / 2 ) ; i ++ ) {
        swap ( v[ i ] , v[ sz - i - 1 ] ) ;
    }
}

void unite ( int val ) {
    int i ;
    for ( i = 0 ; i < n ; i ++ ) {
        aux[ i ] = 0 ;
    }
    int sz = ret.size ( ) ;
    aux[ ret[ sz - 1 ] - 1 ] = 1 ;
    aux[ val - 1 ] = 1 ;
    if ( Query ( aux ) == 2 ) {
        rev ( ret ) ;
    }
    ret.push_back ( val ) ;
}

bool f ( int x ) {
    int i ;
    for ( i = 0 ; i < n ; i ++ ) {
        aux[ i ] = 0 ;
    }
    int sz = ret.size ( ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        aux[ ret[ i ] - 1 ] = 1 ;
    }
    int lft = x ;
    for ( i = 0 ; i < n ; i ++ ) {
        if ( aux[ i ] != 0 ) { continue ; }
        lft -- ;
        aux[ i ] = 1 ;
        if ( lft <= 0 ) { break ; }
    }
    int ans1 = Query ( aux ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        aux[ ret[ i ] - 1 ] = 0 ;
    }
    int ans2 = Query ( aux ) ;
    return ( ans1 <= ans2 ) ;
}


void add ( int id ) {
    int l , r , mid ;
    l = 1 ;
    r = n - id + 1 ;
    int h = ( n - id + 1 ) ;
    while ( l <= r ) {
        int mid = ( l + r ) / 2 ;
        if ( f ( mid ) == true ) { r = mid - 1 ; h = mid ; }
        else { l = mid + 1 ; }
    }
    int i ;
    for ( i = 0 ; i < n ; i ++ ) {
        aux[ i ] = 0 ;
    }
    for ( i = 0 ; i < id - 1 ; i ++ ) {
        aux[ ret[ i ] - 1 ] = 1 ;
    }
    for ( i = 0 ; i < n ; i ++ ) {
        if ( aux[ i ] != 0 ) { continue ; }
        h -- ;
        if ( h == 0 ) {
            unite ( i + 1 ) ;
            return ;
        }
    }
}

void Solve ( int N ) {
    n = N ;
    ret.clear ( ) ;
    ret.push_back ( 1 ) ;
    aux.resize ( n ) ;
    int i ;
    for ( i = 0 ; i < n ; i ++ ) { aux[ i ] = 0 ; }
    for ( i = 2 ; i <= n ; i ++ ) {
        add ( i ) ;
    }
    Answer ( ret ) ;
}

Compilation message (stderr)

library.cpp: In function 'void add(int)':
library.cpp:59:17: warning: unused variable 'mid' [-Wunused-variable]
     int l , r , mid ;
                 ^~~

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