제출 #463652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
463652		MohamedFaresNebili	동굴 (IOI13_cave)	C++14	100 / 100	1595 ms	512 KiB

cave

#include <bits/stdc++.h>
#include"cave.h"
 
using namespace std;
 
/** |||||||||||||||||||||||||||||||| SOLUTION |||||||||||||||||||||||||||||||| **/
 
int n, pos[5024], d[5024], arr[5024];
bitset<5024>done;
 
void div(int v, int l, int r, int col) {
    if(l==r) {
        done[l]=true;
        pos[l]=col; d[l]=v;
        return;
    }
    int mid=(l+r)/2;
    for(int i=0;i<n;i++) {
        if(l<=i&&mid>=i) arr[i]=col;
        else arr[i]=1^col;
    }
    for(int i=0;i<n;i++)
        if(done[i]) arr[i]=pos[i];
    int a=tryCombination(arr);
    if(a==-1||a>v) div(v, l, mid, col);
    else div(v, mid+1, r, col);
}
 
int solve(int i)
{
    for(int l=0;l<n;l++) arr[l]=0;
    for(int l=0;l<n;l++)
        if(done[l]) arr[l]=pos[l];
    int a=tryCombination(arr);
    if(a==-1||a>i) return 0;
    else return 1;
}
 
void exploreCave(int N) {
    n=N;
    for(int l=0;l<n;l++) {
        int a=solve(l);
        div(l, 0, n-1, a);
    }
    answer(pos, d);
}

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