oj.uz

Submission #44336

# Submission time Handle Problem Language Result Execution time Memory
44336 2018-03-31T11:52:29 Z chonka Library (JOI18_library) C++14
19 / 100
 608 ms 716 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 > 1 ) {
        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
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 248 KB Output is correct
2 Correct 51 ms 436 KB Output is correct
3 Correct 63 ms 516 KB Output is correct
4 Correct 60 ms 540 KB Output is correct
5 Correct 54 ms 540 KB Output is correct
6 Correct 49 ms 540 KB Output is correct
7 Correct 53 ms 540 KB Output is correct
8 Correct 50 ms 540 KB Output is correct
9 Correct 54 ms 540 KB Output is correct
10 Correct 30 ms 540 KB Output is correct
11 Correct 2 ms 540 KB Output is correct
12 Correct 2 ms 540 KB Output is correct
13 Correct 2 ms 544 KB Output is correct
14 Correct 2 ms 544 KB Output is correct
15 Correct 3 ms 544 KB Output is correct
16 Correct 5 ms 544 KB Output is correct

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 248 KB Output is correct
2 Correct 51 ms 436 KB Output is correct
3 Correct 63 ms 516 KB Output is correct
4 Correct 60 ms 540 KB Output is correct
5 Correct 54 ms 540 KB Output is correct
6 Correct 49 ms 540 KB Output is correct
7 Correct 53 ms 540 KB Output is correct
8 Correct 50 ms 540 KB Output is correct
9 Correct 54 ms 540 KB Output is correct
10 Correct 30 ms 540 KB Output is correct
11 Correct 2 ms 540 KB Output is correct
12 Correct 2 ms 540 KB Output is correct
13 Correct 2 ms 544 KB Output is correct
14 Correct 2 ms 544 KB Output is correct
15 Correct 3 ms 544 KB Output is correct
16 Correct 5 ms 544 KB Output is correct
17 Incorrect 608 ms 716 KB Wrong Answer [3]
18 Halted 0 ms 0 KB -