| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 349324 |
2021-01-17T12:08:45 Z |
Mefarnis |
Archery (IOI09_archery) |
C++14 |
|
2000 ms |
65540 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200000
#define mod 1000000007
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;
int n,k;
int ar[2*maxn];
int ansLast,ansInit;
void swaps(vector<pi>& vec) {
for( int i = 0 ; i < n ; i++ )
if(vec[i].fi > vec[i].se)
swap(vec[i].fi,vec[i].se);
/*
for( int i = 0 ; i < n ; i++ )
printf("%d %d , ",vec[i].fi,vec[i].se);
puts("");
*/
}
int getHash(vector<pi>& vec) {
LL val = 0;
for( int i = 0 ; i < n ; i++ ) {
val = 2*n*val + vec[i].fi-1;
val = 2*n*val + vec[i].se-1;
val %= mod;
}
return val;
}
bool isSame(vector<pi>& a , vector<pi>& b) {
for( int i = 0 ; i < n ; i++ )
if(a[i] != b[i])
return false;
return true;
}
bool check(vector< vector<pi> >& vecs , vector<pi>& vec , int r , vector<int>& vals , int val) {
for( int i = 0 ; i < r ; i++ )
if(vals[i] == val) {
int len = r-i;
int rem = k-i;
int add = rem % len;
vec = vecs[i+add];
return true;
}
return false;
}
void solve(int t) {
// printf("t = %d\n",t);
vector<pi> vec;
vector<int> vals;
vector< vector<pi> > vecs;
for( int i = 0 ; i < n ; i++ )
vec.pb(pi(0,0));
vec[t].fi = ar[0];
for( int i = 1 , idx = 0 ; i < 2*n ; i++ ) {
if(vec[idx].fi == 0)
vec[idx].fi = ar[i];
else
vec[idx++].se = ar[i];
}
swaps(vec);
vecs.pb(vec);
vals.pb(getHash(vec));
for( int r = 1 ; r <= k ; r++ ) {
vector<pi> last = vec;
for( int i = 1 ; i < n ; i++ ) {
vec[i-1].fi = min(last[i].fi,last[i].se);
vec[i].se = max(last[i].fi,last[i].se);
}
vec[0].se = min(last[0].fi,last[0].se);
vec[n-1].fi = max(last[0].fi,last[0].se);
swaps(vec);
int val = getHash(vec);
if(check(vecs,vec,r,vals,val))
break;
vecs.pb(vec);
vals.pb(getHash(vec));
}
for( int i = 0 ; i < n ; i++ )
if(vec[i].fi == ar[0] || vec[i].se == ar[0]) {
if(i <= ansLast) {
ansLast = i;
ansInit = t;
}
break;
}
}
int main() {
scanf("%d%d",&n,&k);
for( int i = 0 ; i < 2*n ; i++ )
scanf("%d",&ar[i]);
ansLast = n;
for( int t = 0 ; t < n ; t++ )
solve(t);
printf("%d\n",ansInit+1);
return 0;
}
Compilation message
archery.cpp: In function 'int main()':
archery.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
98 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
archery.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
100 | scanf("%d",&ar[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Execution timed out |
2079 ms |
36172 KB |
Time limit exceeded |
| 3 |
Correct |
43 ms |
492 KB |
Output is correct |
| 4 |
Runtime error |
219 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
363 ms |
1068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
276 KB |
Output is correct |
| 2 |
Correct |
395 ms |
1148 KB |
Output is correct |
| 3 |
Execution timed out |
2084 ms |
32064 KB |
Time limit exceeded |
| 4 |
Runtime error |
213 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
246 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Correct |
344 ms |
1224 KB |
Output is correct |
| 7 |
Execution timed out |
2055 ms |
13732 KB |
Time limit exceeded |
| 8 |
Runtime error |
216 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
217 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Execution timed out |
2084 ms |
20600 KB |
Time limit exceeded |
| 11 |
Runtime error |
224 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
222 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
233 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
220 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
217 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Correct |
384 ms |
1320 KB |
Output is correct |
| 17 |
Execution timed out |
2094 ms |
27172 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2086 ms |
64176 KB |
Time limit exceeded |
| 19 |
Runtime error |
216 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
217 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 21 |
Runtime error |
215 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 22 |
Runtime error |
219 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 |
Runtime error |
248 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 24 |
Correct |
407 ms |
1320 KB |
Output is correct |
| 25 |
Execution timed out |
2089 ms |
16252 KB |
Time limit exceeded |
| 26 |
Runtime error |
221 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 27 |
Runtime error |
213 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 28 |
Runtime error |
234 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 29 |
Execution timed out |
2076 ms |
35664 KB |
Time limit exceeded |
| 30 |
Runtime error |
214 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 31 |
Runtime error |
217 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 32 |
Runtime error |
248 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 33 |
Correct |
384 ms |
1184 KB |
Output is correct |
| 34 |
Correct |
393 ms |
1276 KB |
Output is correct |
| 35 |
Runtime error |
220 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 36 |
Runtime error |
219 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 37 |
Runtime error |
217 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 38 |
Runtime error |
221 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 39 |
Correct |
343 ms |
1344 KB |
Output is correct |
| 40 |
Execution timed out |
2096 ms |
16292 KB |
Time limit exceeded |
| 41 |
Runtime error |
238 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 42 |
Runtime error |
221 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 43 |
Runtime error |
217 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 44 |
Runtime error |
215 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 45 |
Runtime error |
215 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 46 |
Runtime error |
214 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 47 |
Runtime error |
250 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
