제출 #29808

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29808		osmanorhan	동굴 (IOI13_cave)	C++14	100 / 100	519 ms	632 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
#define ort (b+s)/2

using namespace std;

const int maxn = 5020;

bool used[maxn];
int ans[maxn], loc[maxn];
int ar[maxn];

void Fill( int b, int e, int t ) {
    for(int i=b;i<=e;i++)
        if( !used[i] ) ar[i] = t;
}

bool look( int b, int e ) {
    for(int i=b;i<=e;i++)
        if( !used[i] ) return 1;
    return 0;
}

int trycom( int ar[] ) {
    int t = tryCombination( ar );
    if( t == -1 ) t = 1e9;
    return t;
}

int find( int n, int b, int s, int val ) {
    if( b == s ) return b;
    if( !look( b, ort ) ) return find( n, ort+1, s, val );
    if( !look( ort+1, s ) ) return find( n, b, ort, val );
    Fill( b, ort, val );
    Fill( ort+1, s, !val );
    if( trycom( ar ) > n ) return find( n, b, ort, val );
    return find( n, ort+1, s, val );
}

void exploreCave(int N) {

    for(int i=0;i<N;i++) {
        Fill( 0, N-1, 0 );
        int val = 0;
        if( trycom( ar ) > i ) val = 0;
        else val = 1;
        int t = find( i, 0, N-1, val );
        loc[t] = i;
        ar[t] = ans[i] = val;
        used[t] = 1;
    }
    answer( ar, loc );
}

• Subtask 1: 12 / 12
• Subtask 2: 13 / 13
• Subtask 3: 21 / 21
• Subtask 4: 30 / 30
• Subtask 5: 24 / 24