제출 #231414

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231414		AASG	동굴 (IOI13_cave)	C++11	100 / 100	244 ms	640 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;
void exploreCave(int N) {
    int n=N;
    int R[n+10];int P[n+10];
    int aux2[n+10];
    int x,y;
    int z=1;
    for(int i=0;i<n;i++){
        R[i]=1;
        P[i]=-1;
    }
    for(int i=0;i<n;i++){
        for(int l=0;l<n;l++){aux2[l]=R[l];}

        int p1=0,p2=n-1;
        x=tryCombination(aux2);z=0;
        while(p1!=p2){
            int p3=(p1+p2)/2;
            if(z==1){
            for(int l=p3+1;l<=p2;l++){
                if(P[l]==-1){
                    aux2[l]=1;
                }
            }}else{
            for(int l=p1;l<=p3;l++){
                if(P[l]==-1){
                    aux2[l]=0;
                }
            }
            }
            y=tryCombination(aux2);
        if(z==1){
            if((x>=i+1 || x==-1) && (y>=i+1 || y==-1)){p2=p3;z=1;}
            else if((x<i+1 && x!=-1) && (y<i+1 && y!=-1)){p2=p3;z=1;}
            else{p1=p3+1;z=0;}
        }else{
            if((x>=i+1 || x==-1) && (y>=i+1 || y==-1)){p1=p3+1;z=0;}
            else if((x<i+1 && x!=-1) && (y<i+1 && y!=-1)){p1=p3+1;z=0;}
            else{p2=p3;z=1;}
        }
        x=y;

        }
        if(x>=i+1 || x==-1){R[p1]=aux2[p1];P[p1]=i;}
        else{
        if(aux2[p1]==1){aux2[p1]=0;}
        else {aux2[p1]=1;}
        R[p1]=aux2[p1];P[p1]=i;
        }
    }
    answer(R,P);
}

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