oj.uz

Submission #284867

# Submission time Handle Problem Language Result Execution time Memory
284867 2020-08-28T07:19:50 Z gs14004 Archery (IOI09_archery) C++17
48 / 100
 2000 ms 512 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 10005;
const int mod = 1e9 + 7;

int n, r, a[MAXN], b[MAXN];

int Do(int r, int s){
	int rot = 0;
	for(int i=0; i<r; i++){
		for(int j=0; j<n; j++){
			if(a[j] > a[j+n]) swap(a[j], a[j+n]);
		}
		swap(a[0], a[n]);
		if(a[0] == s) rot++;
		rotate(a, a + 1, a + n);
	}
	int pos = (find(a, a + 2 * n, s) - a) % n - rot * n;
	return pos;
}

mt19937 rng(0x14004);

int main(){
	scanf("%d %d",&n,&r);
  assert(n <= 5000);
	for(int i=0; i<2*n; i++){
		scanf("%d",&b[i]);
	}
	r = (r % n) + 2 * n;
	int s = 0, e = n - 1;
	auto fn = [&](int i){
		vector<int> foo(b, b + 2 * n);
		rotate(foo.begin(), foo.begin() + 1, foo.begin() + 2 * i + 1);
		for(int i=0; i<n; i++){
			a[i] = foo[2*i];
			a[i+n] = foo[2*i+1];
		}
		return Do(r, b[0]);
	};
	auto Mod = [&](int x){ return (x % n + n) % n; };
	int qq = fn(n - 1);
	while(s != e){
		int m = (s + e) / 2;
		if(fn(m) >= qq - Mod(qq)) e = m;
		else s = m + 1;
	}
	int rr = fn(s);
	s = 0, e = n - 1;
	while(s != e){
		int m = (s + e + 1) / 2;
		if(fn(m) <= rr) s = m;
		else e = m - 1;
	}
	cout << s + 1 << endl;
}

Compilation message

archery.cpp: In function 'int main()':
archery.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  scanf("%d %d",&n,&r);
      |  ~~~~~^~~~~~~~~~~~~~~
archery.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d",&b[i]);
      |   ~~~~~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 503 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1171 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct

Subtask #2
42.0 / 94.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 406 ms 420 KB Output is correct
4 Runtime error 1 ms 512 KB Execution killed with signal 11
5 Runtime error 1 ms 512 KB Execution killed with signal 11
6 Correct 3 ms 384 KB Output is correct
7 Correct 127 ms 384 KB Output is correct
8 Runtime error 1 ms 512 KB Execution killed with signal 11
9 Runtime error 1 ms 512 KB Execution killed with signal 11
10 Correct 228 ms 384 KB Output is correct
11 Runtime error 1 ms 512 KB Execution killed with signal 11
12 Correct 1200 ms 384 KB Output is correct
13 Runtime error 1 ms 512 KB Execution killed with signal 11
14 Execution timed out 2091 ms 512 KB Time limit exceeded
15 Runtime error 1 ms 512 KB Execution killed with signal 11
16 Correct 3 ms 384 KB Output is correct
17 Correct 307 ms 388 KB Output is correct
18 Correct 709 ms 384 KB Output is correct
19 Execution timed out 2075 ms 384 KB Time limit exceeded
20 Execution timed out 2090 ms 512 KB Time limit exceeded
21 Runtime error 1 ms 512 KB Execution killed with signal 11
22 Runtime error 1 ms 512 KB Execution killed with signal 11
23 Runtime error 1 ms 512 KB Execution killed with signal 11
24 Correct 4 ms 384 KB Output is correct
25 Correct 161 ms 384 KB Output is correct
26 Execution timed out 2080 ms 512 KB Time limit exceeded
27 Runtime error 1 ms 512 KB Execution killed with signal 11
28 Runtime error 1 ms 512 KB Execution killed with signal 11
29 Correct 361 ms 384 KB Output is correct
30 Execution timed out 2045 ms 512 KB Time limit exceeded
31 Runtime error 1 ms 512 KB Execution killed with signal 11
32 Runtime error 1 ms 512 KB Execution killed with signal 11
33 Correct 3 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 877 ms 504 KB Output is correct
36 Correct 1361 ms 384 KB Output is correct
37 Runtime error 1 ms 512 KB Execution killed with signal 11
38 Runtime error 1 ms 512 KB Execution killed with signal 11
39 Correct 3 ms 384 KB Output is correct
40 Correct 178 ms 384 KB Output is correct
41 Correct 668 ms 504 KB Output is correct
42 Correct 1147 ms 448 KB Output is correct
43 Execution timed out 2043 ms 512 KB Time limit exceeded
44 Runtime error 1 ms 512 KB Execution killed with signal 11
45 Runtime error 1 ms 512 KB Execution killed with signal 11
46 Runtime error 1 ms 512 KB Execution killed with signal 11
47 Runtime error 1 ms 512 KB Execution killed with signal 11