oj.uz

Submission #44334

# Submission time Handle Problem Language Result Execution time Memory
44334 2018-03-31T11:48:41 Z chonka Library (JOI18_library) C++14
0 / 100
 308 ms 488 KB 
#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 ;
    while ( r - l > 3 ) {
        int mid = ( l + r ) / 2 ;
        if ( f ( mid ) == true ) { r = mid ; }
        else { l = mid ; }
    }
    while ( f ( l ) == false ) { l ++ ; }
    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 ; }
        l -- ;
        if ( l == 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

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

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 248 KB Output is correct
2 Correct 43 ms 440 KB Output is correct
3 Runtime error 308 ms 488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 248 KB Output is correct
2 Correct 43 ms 440 KB Output is correct
3 Runtime error 308 ms 488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -