Submission #81338

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
81338	2018-10-24 12:36:41	anaonoprishvili	Cave (IOI13_cave)	C++14	100 / 100	442 ms	692 KiB

cave

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "cave.h"
#include<bits/stdc++.h>
int ans[50005],ans1[50005],s[50005],fix[50005];
void exploreCave(int N)
{
    for(int i=0; i<N; i++)
    {
      for(int j=0;j<N;j++) if(fix[j]==1) s[j]=ans[j]; else s[j]=0;
    int x=tryCombination(s);
      int k=0;
    if(x==-1 || x>i) k=1; 
    int t=k, l=0, r=N-1, p=0;
    while(l<=r)
    {
      int m=(l+r)/2;
      for(int j=l;j<=m;j++)
      if(fix[j]==0) s[j]=1-s[j];      
      x=tryCombination(s);
        int c=0;
      if(x==-1 || x>i) c=1;     
      if(k!=c) r=m-1, p=m;
      else l=m+1;
      k=c;
    }
    ans1[p]=i; fix[p]=1;
    if (t==1) ans[p]=0; else ans[p]=1;
  }
  answer(ans,ans1);
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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