# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
817896 |
2023-08-09T19:26:34 Z |
ALeonidou |
Cave (IOI13_cave) |
C++17 |
|
149 ms |
444 KB |
#include "cave.h"
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <bitset>
#include <string>
#include <fstream>
#include <cstring>
#include <cassert>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define ll int
#define llu unsigned long long
#define ld long double
#define F first
#define S second
#define endl "\n"
#define MID ((l+r)/2)
#define sorv(a) sort(a.begin(),a.end())
#define revv(a) reverse(a.begin(),a.end())
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define ins insert
#define pb push_back
#define inf 1e9
#define INF 1e18
#define MOD 1000000007
#define MOD2 998244353
typedef pair <ll, ll> ii;
typedef pair <ll,ii> iii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <iii> viii;
typedef set <ll> si;
typedef map <ll,ll> mi;
#ifndef ONLINE_JUDGE
//#define ONLINE_JUDGE
#endif
#ifndef ONLINE_JUDGE
template<typename T>void printArr(T *arr,ll l,ll m=0){if(m==1){for(ll i=0;i<l;i++)cout<<arr[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<l;i++)cout<<i<<": "<<arr[i]<<endl;}}
#define printArr2D(arr,n,m)cout<<endl;for(ll i=0;i<n;i++){for(ll j=0;j<m;j++)cout<<arr[i][j]<<" ";cout<<endl;}cout<<endl;
template<typename T>void printVct(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i]<<" ";cout<<endl;}else{cout<<endl;for(ll i=0; i<sz(v);i++)cout<<i<<": "<<v[i]<<endl;}}
template<typename T>void printVct2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j]<<" ";cout<<endl;}}
template<typename T>void printVctPair(vector<T> v,ll m=0){if(m==1){for(ll i=0;i<sz(v);i++)cout<<v[i].F<<":"<<v[i].S<<" ";cout<<endl;}else{cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<": "<<v[i].F<<" : "<<v[i].S<<endl;}}
template<typename T>void printVctPair2D(vector<vector<T> >v){cout<<endl;for(ll i=0;i<sz(v);i++){cout<<i<<": ";for(ll j=0;j<sz(v[i]);j++)cout<<v[i][j].F<<":"<<v[i][j].S<<" ";cout<<endl;}}
template<typename T>void printVctPair3(vector<T> v,ll m=0){cout<<endl;for(ll i=0;i<sz(v);i++)cout<<i<<": ("<<v[i].F<<" : "<<v[i].S.F<<" : "<<v[i].S.S<<")"<<endl;}
template<typename T1,typename T2>void printMap(map<T1,T2>mp){cout<<endl;for(typename map<T1,T2>::iterator it=mp.begin();it!=mp.end();it++)cout<<it->F<<" -> "<<it->S<<endl;}
template<typename T>void printSet(set<T>st,ll m=0){typename set<T>::iterator it;if(m){for(it=st.begin();it!=st.end();it++)cout<<*it<<" ";cout<<endl;}else{cout<<endl;for(it=st.begin();it!=st.end();it++)cout<<*it<<endl;}}
void check(ll n){cout<<"CHECKPOINT "<<n<<"\n\n";}
#define dbg(x) cout<<#x<<":"<<x<<endl
#define dbg2(x,y) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define dbg3(x,y,z) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define dbg4(x,y,z,w) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<endl
#define dbg5(x,y,z,w,v) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<" "<<#v<<":"<<v<<endl
#define dbg6(x,y,z,w,v,u) cout<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<" "<<#w<<":"<<w<<" "<<#v<<":"<<v<<" "<<#u<<":"<<u<<endl
#define dbgp(x) cout<<#x<<":("<<x.F<<" "<<x.S<<")"<<endl
#define dbgp2(x,y) cout<<#x<<":("<<x.F<<","<<x.S<<") "<<#y<<":("<<y.F<<","<<y.S<<")"<<endl
#define dbgt(x) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<")"<<endl
#define dbgt2(x,y) cout<<#x<<":("<<x.F<<" "<<x.S.F<<" "<<x.S.S<<") "<<#y<<":("<<y.F<<" "<<y.S.F<<" "<<y.S.S<<")"<<endl
#else
template<typename T>void printArr(T *arr,ll l,ll m=0){}
#define printArr2D(arr,n,m)
template<typename T>void printVct(vector<T> v,ll m=0){}
template<typename T>void printVct2D(vector<vector<T> >v){}
template<typename T>void printVctPair(vector<T> v,ll m=0){}
template<typename T>void printVctPair2D(vector<vector<T> >v){}
template<typename T>void printVctPair3(vector<T> v,ll m=0){}
template<typename T1,typename T2>void printMap(map<T1,T2>mp){}
template<typename T>void printSet(set<T>st,ll m=0){}
void check(ll n){}
#define dbg(x)
#define dbg2(x,y)
#define dbg3(x,y,z)
#define dbg4(x,y,z,w)
#define dbg5(x,y,z,w,v)
#define dbg6(x,y,z,w,v,u)
#define dbgp(x)
#define dbgp2(x,y)
#define dbgt(x)
#define dbgt2(x,y)
#endif
const ll dx[8]={1,-1,0,0,1,1,-1,-1}, dy[8]={0,0,1,-1,1,-1,1,-1};
ll charToIntNum(char c){return (ll)c-48;}
char intToCharNum(ll n){return (char)n+48;}
ll charToIntLower(char c){return (ll)c-97;}
char intToCharLower(ll n){return (char)n+97;}
ll charToIntUpper(char c){return (ll)c-65;}
char intToCharUpper(ll n){return (char)n+65;}
void tabb(ll n){for(ll i=0;i<n;i++)cout<<"\t";}
ll gcd(ll x,ll y){if(y==0)return x;return gcd(y,x%y);}
void yesno(bool a){if(a){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}
void exploreCave(ll n) {
ll tmp[n], s[n], d[n];
//part 1: find correct switch configuration in O(nlogn)
//init
//loop
//bs
//build (keeping locked unchaned)
//check
//lock
for (ll i=0; i<n; i++)
s[i] = -1;
for (ll i=0; i<n; i++)
d[i] = -1;
// cout<<"s: "; printArr(s,n,1);
// cout<<"d: "; printArr(d,n,1);
ll prev,cur;
for (ll i=1; i<=n; i++){
// dbg(i);
for (ll j= 0; j<n; j++){
if (s[j] == -1){
tmp[j] = 0;
}
else{
tmp[j] = s[j];
}
}
// cout<<"tmp: ";
// printArr(tmp,n,1);
prev = min(tryCombination(tmp), i);
if (prev == -1) prev = i;
cur = prev; //for case n = 1
ll l = 0, r = n-1, mid;
while (l < r){
// cout<<endl;
mid = MID;
//build
for (ll j = l; j<=mid; j++){
if (s[j] == -1){
tmp[j] = !tmp[j];
}
}
// dbg3(l,r,mid);
// cout<<"tmp: ";
// printArr(tmp,n,1);
//check
cur = min(tryCombination(tmp), i);
if (cur == -1) cur = i;
if (prev == cur){
//right
l = mid+1;
}
else{
//left
r = mid;
}
// dbg2(prev, cur);
prev = cur;
}
if (cur == i) s[l] = tmp[l];
else s[l] = !tmp[l];
d[l] = i-1;
// cout<<"s: "; printArr(s,n,1);
// cout<<"d: "; printArr(d,n,1);
// cout<<endl<<endl<<endl;
}
// cout<<endl<<endl;
answer(s,d);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
380 KB |
Output is correct |
2 |
Correct |
81 ms |
380 KB |
Output is correct |
3 |
Correct |
138 ms |
392 KB |
Output is correct |
4 |
Correct |
85 ms |
380 KB |
Output is correct |
5 |
Correct |
146 ms |
388 KB |
Output is correct |
6 |
Correct |
121 ms |
392 KB |
Output is correct |
7 |
Correct |
131 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
0 ms |
224 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
122 ms |
424 KB |
Output is correct |
13 |
Correct |
128 ms |
428 KB |
Output is correct |
14 |
Correct |
124 ms |
444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
392 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
129 ms |
388 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
131 ms |
388 KB |
Output is correct |
7 |
Correct |
133 ms |
340 KB |
Output is correct |
8 |
Correct |
147 ms |
388 KB |
Output is correct |
9 |
Correct |
147 ms |
392 KB |
Output is correct |
10 |
Correct |
149 ms |
396 KB |
Output is correct |
11 |
Correct |
134 ms |
388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
19 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
20 ms |
348 KB |
Output is correct |
24 |
Correct |
20 ms |
340 KB |
Output is correct |
25 |
Correct |
20 ms |
352 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
19 ms |
352 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
19 ms |
352 KB |
Output is correct |
31 |
Correct |
19 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
22 ms |
340 KB |
Output is correct |
36 |
Correct |
20 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
380 KB |
Output is correct |
2 |
Correct |
81 ms |
380 KB |
Output is correct |
3 |
Correct |
138 ms |
392 KB |
Output is correct |
4 |
Correct |
85 ms |
380 KB |
Output is correct |
5 |
Correct |
146 ms |
388 KB |
Output is correct |
6 |
Correct |
121 ms |
392 KB |
Output is correct |
7 |
Correct |
131 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
0 ms |
224 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
122 ms |
424 KB |
Output is correct |
13 |
Correct |
128 ms |
428 KB |
Output is correct |
14 |
Correct |
124 ms |
444 KB |
Output is correct |
15 |
Correct |
131 ms |
392 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
129 ms |
388 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
131 ms |
388 KB |
Output is correct |
21 |
Correct |
133 ms |
340 KB |
Output is correct |
22 |
Correct |
147 ms |
388 KB |
Output is correct |
23 |
Correct |
147 ms |
392 KB |
Output is correct |
24 |
Correct |
149 ms |
396 KB |
Output is correct |
25 |
Correct |
134 ms |
388 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
0 ms |
212 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
0 ms |
212 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
0 ms |
212 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
0 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
0 ms |
212 KB |
Output is correct |
42 |
Correct |
0 ms |
212 KB |
Output is correct |
43 |
Correct |
0 ms |
212 KB |
Output is correct |
44 |
Correct |
0 ms |
212 KB |
Output is correct |
45 |
Correct |
19 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
212 KB |
Output is correct |
47 |
Correct |
0 ms |
212 KB |
Output is correct |
48 |
Correct |
20 ms |
348 KB |
Output is correct |
49 |
Correct |
20 ms |
340 KB |
Output is correct |
50 |
Correct |
20 ms |
352 KB |
Output is correct |
51 |
Correct |
0 ms |
212 KB |
Output is correct |
52 |
Correct |
0 ms |
212 KB |
Output is correct |
53 |
Correct |
19 ms |
352 KB |
Output is correct |
54 |
Correct |
0 ms |
212 KB |
Output is correct |
55 |
Correct |
19 ms |
352 KB |
Output is correct |
56 |
Correct |
19 ms |
340 KB |
Output is correct |
57 |
Correct |
0 ms |
212 KB |
Output is correct |
58 |
Correct |
0 ms |
212 KB |
Output is correct |
59 |
Correct |
0 ms |
212 KB |
Output is correct |
60 |
Correct |
22 ms |
340 KB |
Output is correct |
61 |
Correct |
20 ms |
340 KB |
Output is correct |
62 |
Correct |
0 ms |
212 KB |
Output is correct |
63 |
Correct |
80 ms |
416 KB |
Output is correct |
64 |
Correct |
81 ms |
340 KB |
Output is correct |
65 |
Correct |
125 ms |
340 KB |
Output is correct |
66 |
Correct |
84 ms |
364 KB |
Output is correct |
67 |
Correct |
131 ms |
340 KB |
Output is correct |
68 |
Correct |
120 ms |
432 KB |
Output is correct |
69 |
Correct |
132 ms |
340 KB |
Output is correct |
70 |
Correct |
1 ms |
212 KB |
Output is correct |
71 |
Correct |
0 ms |
308 KB |
Output is correct |
72 |
Correct |
123 ms |
432 KB |
Output is correct |
73 |
Correct |
127 ms |
340 KB |
Output is correct |
74 |
Correct |
123 ms |
364 KB |
Output is correct |
75 |
Correct |
129 ms |
340 KB |
Output is correct |
76 |
Correct |
0 ms |
212 KB |
Output is correct |
77 |
Correct |
1 ms |
212 KB |
Output is correct |
78 |
Correct |
132 ms |
340 KB |
Output is correct |
79 |
Correct |
137 ms |
432 KB |
Output is correct |
80 |
Correct |
146 ms |
428 KB |
Output is correct |
81 |
Correct |
146 ms |
428 KB |
Output is correct |
82 |
Correct |
146 ms |
432 KB |
Output is correct |
83 |
Correct |
135 ms |
340 KB |
Output is correct |
84 |
Correct |
1 ms |
212 KB |
Output is correct |
85 |
Correct |
19 ms |
376 KB |
Output is correct |
86 |
Correct |
120 ms |
320 KB |
Output is correct |
87 |
Correct |
1 ms |
212 KB |
Output is correct |
88 |
Correct |
0 ms |
212 KB |
Output is correct |
89 |
Correct |
24 ms |
348 KB |
Output is correct |
90 |
Correct |
20 ms |
372 KB |
Output is correct |
91 |
Correct |
20 ms |
368 KB |
Output is correct |
92 |
Correct |
139 ms |
340 KB |
Output is correct |
93 |
Correct |
139 ms |
340 KB |
Output is correct |
94 |
Correct |
139 ms |
428 KB |
Output is correct |
95 |
Correct |
0 ms |
212 KB |
Output is correct |
96 |
Correct |
1 ms |
308 KB |
Output is correct |
97 |
Correct |
121 ms |
432 KB |
Output is correct |
98 |
Correct |
19 ms |
340 KB |
Output is correct |
99 |
Correct |
120 ms |
444 KB |
Output is correct |
100 |
Correct |
0 ms |
308 KB |
Output is correct |
101 |
Correct |
19 ms |
368 KB |
Output is correct |
102 |
Correct |
19 ms |
364 KB |
Output is correct |
103 |
Correct |
121 ms |
432 KB |
Output is correct |
104 |
Correct |
0 ms |
212 KB |
Output is correct |
105 |
Correct |
0 ms |
212 KB |
Output is correct |
106 |
Correct |
0 ms |
212 KB |
Output is correct |
107 |
Correct |
20 ms |
340 KB |
Output is correct |
108 |
Correct |
20 ms |
340 KB |
Output is correct |
109 |
Correct |
138 ms |
320 KB |
Output is correct |
110 |
Correct |
138 ms |
432 KB |
Output is correct |
111 |
Correct |
1 ms |
212 KB |
Output is correct |