# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
239842 | 2020-06-17T11:46:02 Z | Dremix10 | Cave (IOI13_cave) | C++17 | 237 ms | 632 KB |
#include "cave.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; #define F first #define S second #define endl '\n' #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define maxp 22 #define EPS (ld)(1e-18) #define mod (int)(1e9+7) void exploreCave(int N) { //cout<<N<<endl; int query[N]; int i,j; int switches[N]; for(i=0;i<N;i++) switches[i]=-1; int door[N];int toSwitch[N]; for(i=0;i<N;i++){ door[i]=-1; toSwitch[i]=-1; } // cout<<last<<endl; for(i=0;i<N;i++){ for(j=0;j<N;j++) if(switches[j]==-1) query[j]=0; else query[j]=switches[j]; //for(j=0;j<N;j++) // cout<<query[j]<<" "; //cout<<endl; int last=tryCombination(query); bool open=true; if(last==i) open=false; //cout<<last<<" "<<open<<endl; int l=0,r=N-1; //int mm=-1; //int one=-1; //cout<<open<<" "<<i<<endl; while(l<r){ int mid=(l+r)/2; for(j=l;j<=mid;j++) if(switches[j]==-1) query[j]^=1; int x=tryCombination(query); //cout<<l<<" "<<r<<" "<<mid<<" "<<x<<" "<<open<<endl; if((open && x<=i && x!=-1) || (!open && (x>i || x==-1))){ r=mid; //mm=mid; open^=1; //if((query[r]==1 && !open) || (query[r]==0 && open)) // one=true; //else // one=false; } else l=mid+1; } int mm=r; if(r-l==1){ if(switches[l]==-1) query[l]^=1; int x=tryCombination(query); if((open && x<=i && x!=-1) || (!open && (x>i || x==-1))){ mm=l; open^=1; } } //cout<<"ans"<<endl; //cout<<open<<" "<<mm<<" "<<query[mm]<<endl; //cout<<l<<" "<<r<<endl; bool one; door[mm]=i; if((query[mm]==1 && open) || (query[mm]==0 && !open)) one=true; else one=false; if(one) switches[mm]=1; else switches[mm]=0; //cout<<"ans "<<i<<": "<<mm<<" "<<switches[mm]<<endl; //cout<<switches[mm]<<endl; } answer(switches,door); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 504 KB | Output is correct |
2 | Correct | 120 ms | 504 KB | Output is correct |
3 | Correct | 175 ms | 512 KB | Output is correct |
4 | Correct | 120 ms | 504 KB | Output is correct |
5 | Correct | 195 ms | 632 KB | Output is correct |
6 | Correct | 177 ms | 632 KB | Output is correct |
7 | Correct | 192 ms | 512 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 4 ms | 384 KB | Output is correct |
10 | Correct | 4 ms | 256 KB | Output is correct |
11 | Correct | 5 ms | 384 KB | Output is correct |
12 | Correct | 176 ms | 512 KB | Output is correct |
13 | Correct | 172 ms | 512 KB | Output is correct |
14 | Correct | 175 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 186 ms | 512 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 187 ms | 512 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 185 ms | 512 KB | Output is correct |
7 | Correct | 189 ms | 512 KB | Output is correct |
8 | Correct | 237 ms | 632 KB | Output is correct |
9 | Correct | 232 ms | 512 KB | Output is correct |
10 | Correct | 235 ms | 632 KB | Output is correct |
11 | Correct | 190 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 256 KB | Output is correct |
9 | Correct | 5 ms | 384 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 5 ms | 384 KB | Output is correct |
12 | Correct | 5 ms | 512 KB | Output is correct |
13 | Correct | 5 ms | 384 KB | Output is correct |
14 | Correct | 5 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 256 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 256 KB | Output is correct |
9 | Correct | 5 ms | 384 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 5 ms | 384 KB | Output is correct |
12 | Correct | 5 ms | 512 KB | Output is correct |
13 | Correct | 5 ms | 384 KB | Output is correct |
14 | Correct | 5 ms | 256 KB | Output is correct |
15 | Correct | 4 ms | 256 KB | Output is correct |
16 | Correct | 5 ms | 384 KB | Output is correct |
17 | Correct | 4 ms | 256 KB | Output is correct |
18 | Correct | 4 ms | 384 KB | Output is correct |
19 | Correct | 5 ms | 256 KB | Output is correct |
20 | Correct | 30 ms | 384 KB | Output is correct |
21 | Correct | 5 ms | 384 KB | Output is correct |
22 | Correct | 5 ms | 384 KB | Output is correct |
23 | Correct | 36 ms | 384 KB | Output is correct |
24 | Correct | 35 ms | 384 KB | Output is correct |
25 | Correct | 34 ms | 384 KB | Output is correct |
26 | Correct | 5 ms | 256 KB | Output is correct |
27 | Correct | 5 ms | 384 KB | Output is correct |
28 | Correct | 30 ms | 384 KB | Output is correct |
29 | Correct | 5 ms | 384 KB | Output is correct |
30 | Correct | 30 ms | 384 KB | Output is correct |
31 | Correct | 30 ms | 384 KB | Output is correct |
32 | Correct | 5 ms | 384 KB | Output is correct |
33 | Correct | 5 ms | 384 KB | Output is correct |
34 | Correct | 5 ms | 384 KB | Output is correct |
35 | Correct | 34 ms | 384 KB | Output is correct |
36 | Correct | 37 ms | 384 KB | Output is correct |
37 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 116 ms | 504 KB | Output is correct |
2 | Correct | 120 ms | 504 KB | Output is correct |
3 | Correct | 175 ms | 512 KB | Output is correct |
4 | Correct | 120 ms | 504 KB | Output is correct |
5 | Correct | 195 ms | 632 KB | Output is correct |
6 | Correct | 177 ms | 632 KB | Output is correct |
7 | Correct | 192 ms | 512 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 4 ms | 384 KB | Output is correct |
10 | Correct | 4 ms | 256 KB | Output is correct |
11 | Correct | 5 ms | 384 KB | Output is correct |
12 | Correct | 176 ms | 512 KB | Output is correct |
13 | Correct | 172 ms | 512 KB | Output is correct |
14 | Correct | 175 ms | 512 KB | Output is correct |
15 | Correct | 186 ms | 512 KB | Output is correct |
16 | Correct | 5 ms | 384 KB | Output is correct |
17 | Correct | 187 ms | 512 KB | Output is correct |
18 | Correct | 4 ms | 384 KB | Output is correct |
19 | Correct | 5 ms | 384 KB | Output is correct |
20 | Correct | 185 ms | 512 KB | Output is correct |
21 | Correct | 189 ms | 512 KB | Output is correct |
22 | Correct | 237 ms | 632 KB | Output is correct |
23 | Correct | 232 ms | 512 KB | Output is correct |
24 | Correct | 235 ms | 632 KB | Output is correct |
25 | Correct | 190 ms | 512 KB | Output is correct |
26 | Correct | 4 ms | 384 KB | Output is correct |
27 | Correct | 5 ms | 256 KB | Output is correct |
28 | Correct | 5 ms | 256 KB | Output is correct |
29 | Correct | 4 ms | 384 KB | Output is correct |
30 | Correct | 5 ms | 384 KB | Output is correct |
31 | Correct | 5 ms | 384 KB | Output is correct |
32 | Correct | 5 ms | 384 KB | Output is correct |
33 | Correct | 5 ms | 256 KB | Output is correct |
34 | Correct | 5 ms | 384 KB | Output is correct |
35 | Correct | 5 ms | 384 KB | Output is correct |
36 | Correct | 5 ms | 384 KB | Output is correct |
37 | Correct | 5 ms | 512 KB | Output is correct |
38 | Correct | 5 ms | 384 KB | Output is correct |
39 | Correct | 5 ms | 256 KB | Output is correct |
40 | Correct | 4 ms | 256 KB | Output is correct |
41 | Correct | 5 ms | 384 KB | Output is correct |
42 | Correct | 4 ms | 256 KB | Output is correct |
43 | Correct | 4 ms | 384 KB | Output is correct |
44 | Correct | 5 ms | 256 KB | Output is correct |
45 | Correct | 30 ms | 384 KB | Output is correct |
46 | Correct | 5 ms | 384 KB | Output is correct |
47 | Correct | 5 ms | 384 KB | Output is correct |
48 | Correct | 36 ms | 384 KB | Output is correct |
49 | Correct | 35 ms | 384 KB | Output is correct |
50 | Correct | 34 ms | 384 KB | Output is correct |
51 | Correct | 5 ms | 256 KB | Output is correct |
52 | Correct | 5 ms | 384 KB | Output is correct |
53 | Correct | 30 ms | 384 KB | Output is correct |
54 | Correct | 5 ms | 384 KB | Output is correct |
55 | Correct | 30 ms | 384 KB | Output is correct |
56 | Correct | 30 ms | 384 KB | Output is correct |
57 | Correct | 5 ms | 384 KB | Output is correct |
58 | Correct | 5 ms | 384 KB | Output is correct |
59 | Correct | 5 ms | 384 KB | Output is correct |
60 | Correct | 34 ms | 384 KB | Output is correct |
61 | Correct | 37 ms | 384 KB | Output is correct |
62 | Correct | 5 ms | 384 KB | Output is correct |
63 | Correct | 117 ms | 536 KB | Output is correct |
64 | Correct | 117 ms | 512 KB | Output is correct |
65 | Correct | 178 ms | 524 KB | Output is correct |
66 | Correct | 129 ms | 504 KB | Output is correct |
67 | Correct | 213 ms | 512 KB | Output is correct |
68 | Correct | 176 ms | 632 KB | Output is correct |
69 | Correct | 190 ms | 524 KB | Output is correct |
70 | Correct | 5 ms | 256 KB | Output is correct |
71 | Correct | 4 ms | 384 KB | Output is correct |
72 | Correct | 174 ms | 632 KB | Output is correct |
73 | Correct | 181 ms | 512 KB | Output is correct |
74 | Correct | 172 ms | 512 KB | Output is correct |
75 | Correct | 188 ms | 632 KB | Output is correct |
76 | Correct | 5 ms | 384 KB | Output is correct |
77 | Correct | 4 ms | 384 KB | Output is correct |
78 | Correct | 187 ms | 632 KB | Output is correct |
79 | Correct | 190 ms | 632 KB | Output is correct |
80 | Correct | 220 ms | 512 KB | Output is correct |
81 | Correct | 219 ms | 512 KB | Output is correct |
82 | Correct | 226 ms | 512 KB | Output is correct |
83 | Correct | 190 ms | 512 KB | Output is correct |
84 | Correct | 5 ms | 384 KB | Output is correct |
85 | Correct | 29 ms | 384 KB | Output is correct |
86 | Correct | 168 ms | 512 KB | Output is correct |
87 | Correct | 5 ms | 256 KB | Output is correct |
88 | Correct | 5 ms | 256 KB | Output is correct |
89 | Correct | 35 ms | 384 KB | Output is correct |
90 | Correct | 36 ms | 384 KB | Output is correct |
91 | Correct | 35 ms | 384 KB | Output is correct |
92 | Correct | 218 ms | 512 KB | Output is correct |
93 | Correct | 224 ms | 632 KB | Output is correct |
94 | Correct | 223 ms | 512 KB | Output is correct |
95 | Correct | 5 ms | 384 KB | Output is correct |
96 | Correct | 5 ms | 256 KB | Output is correct |
97 | Correct | 177 ms | 512 KB | Output is correct |
98 | Correct | 33 ms | 384 KB | Output is correct |
99 | Correct | 174 ms | 528 KB | Output is correct |
100 | Correct | 4 ms | 384 KB | Output is correct |
101 | Correct | 30 ms | 384 KB | Output is correct |
102 | Correct | 31 ms | 384 KB | Output is correct |
103 | Correct | 169 ms | 512 KB | Output is correct |
104 | Correct | 5 ms | 256 KB | Output is correct |
105 | Correct | 5 ms | 384 KB | Output is correct |
106 | Correct | 5 ms | 384 KB | Output is correct |
107 | Correct | 34 ms | 384 KB | Output is correct |
108 | Correct | 37 ms | 384 KB | Output is correct |
109 | Correct | 231 ms | 632 KB | Output is correct |
110 | Correct | 223 ms | 632 KB | Output is correct |
111 | Correct | 4 ms | 384 KB | Output is correct |