Submission #167541

#	Time	Username	Problem	Language	Result	Execution time	Memory
167541		wildturtle	Cave (IOI13_cave)	C++14	100 / 100	1398 ms	652 KiB

cave

#include"cave.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,i,n,A[200005],B[200005],C[200005],D[200005],mid,le,ri;
int go(int x,int y) {
           for(int i=0;i<n;i++) {
                      if(B[i]>0) A[i]=B[i]-1;
                      else { if(x<=i && i<=y) A[i]=1;
                                 else A[i]=0;
                      }
           }
           return tryCombination(A);
}
int go1(int x,int y) {
           for(int i=0;i<n;i++) {
                      if(B[i]>0) A[i]=B[i]-1;
                      else { if(x>i || i>y) A[i]=1;
                                 else A[i]=0;
                      }
           }           
           return tryCombination(A);
}
void exploreCave(int N) {
           n=N;
           for(int i=0;i<n;i++) {
                      le=0; ri=n-1;
                      a=0;
                      c=go(0,n-1);
                      if(c>i || c==-1) a=1;
                      while(le<ri) {
                                 mid=(le+ri)/2;
                                 if(a==1) {
                                            c=go(le,mid);
                                            if(c>i || c==-1) ri=mid;
                                            else le=mid+1;
                                 }
                                 else {
                                            c=go1(le,mid);
                                            if(c>i || c==-1) ri=mid;
                                            else le=mid+1;
                                 }
                      }
                      if(a==1) B[le]=2;
                      else B[le]=1;
                      C[le]=a;
                      D[le]=i;
           }
           answer(C,D);
}

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