oj.uz

Submission #424656

# Submission time Handle Problem Language Result Execution time Memory
424656 2021-06-12T08:44:06 Z saleh The Big Prize (IOI17_prize) C++17
20 / 100
 145 ms 15236 KB 
#include "prize.h"
#include <bits/stdc++.h>


using namespace std;

const int MAXN = 200 * 1000 + 23;





/*
int m, a[MAXN];
vector<int> ask(int x) {
	vector<int> v;
	v.push_back(0);
	for (int i = 0; i < x; i++) if (a[i] < a[x]) v.back()++;
	v.push_back(0);
	for (int i = x; i < m; i++) if (a[i] < a[x]) v.back()++;
	return v;
}*/





vector<int> vec[MAXN];
bitset<MAXN> mark;
int look = 0, javab = -1, n, sum[MAXN];
set<int> lft;

vector<int> osk(int x) {
	if (mark[x]) return vec[x];
	mark[x] = true;
	lft.erase(x);
	return vec[x] = ask(x);
}
bool go() {
	int dw = 0, up = n, l = 0, r = 0;
	while (up - dw > 1) {
		int mid = (dw + up) >> 1;
		if (mark[mid] && vec[mid][0] + vec[mid][1] < look) {//opt if tle
			auto tmp = lft.lower_bound(mid);
			if (*tmp >= up) tmp--;
			mid = *tmp;
		}
		vector<int> v = osk(mid);
//		cout << mid << ' ' << v[0] << ' ' << v[1] << endl;
		if (v[0] + v[1] == 0) return javab = mid, true;
		if (v[0] + v[1] < look) return false;
		if (look < v[0] + v[1]) {
			look = v[0] + v[1];
			for (int i = 1; i <= n; i++) if (mark[i] && i != mid) sum[i] = sum[i - 1] + 1; else sum[i] = sum[i - 1];
		}
		int ll = v[0] - l - (sum[mid] - sum[dw]), rr = v[1] - r - (sum[up] - sum[mid]);
//		cout << '\\' << ll << ' ' << rr << endl;
		if (ll < rr) dw = mid;
		else up = mid;
	}
		vector<int> v = osk(dw);
		if (v[0] + v[1] == 0) return javab = dw, true;
		if (v[0] + v[1] < look) return false;
		if (look < v[0] + v[1]) {
			look = v[0] + v[1];
			for (int i = 1; i <= n; i++) if (mark[i] && i != dw) sum[i] = sum[i - 1] + 1; else sum[i] = sum[i - 1];
		}
}

int find_best(int N) {
	n = N;
	for (int i = 0; i < n; i++) lft.insert(i);
	while (!go());
	return javab;
}
/*
int main() {
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) cin >> a[i];
	cout << find_best(m);
	return 0;
}*/

Compilation message

prize.cpp: In function 'bool go()':
prize.cpp:61:25: warning: control reaches end of non-void function [-Wreturn-type]
   61 |   vector<int> v = osk(dw);
      |                         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15164 KB Output is correct
2 Correct 52 ms 15236 KB Output is correct
3 Correct 51 ms 15164 KB Output is correct
4 Correct 53 ms 15040 KB Output is correct
5 Correct 51 ms 14272 KB Output is correct
6 Correct 53 ms 15088 KB Output is correct
7 Correct 50 ms 14300 KB Output is correct
8 Correct 51 ms 14384 KB Output is correct
9 Correct 52 ms 15148 KB Output is correct
10 Correct 60 ms 15164 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 15096 KB Output is correct
2 Correct 52 ms 15072 KB Output is correct
3 Correct 53 ms 15092 KB Output is correct
4 Correct 62 ms 15084 KB Output is correct
5 Correct 49 ms 14288 KB Output is correct
6 Correct 51 ms 15040 KB Output is correct
7 Correct 50 ms 14368 KB Output is correct
8 Correct 56 ms 14480 KB Output is correct
9 Correct 53 ms 15164 KB Output is correct
10 Correct 52 ms 15040 KB Output is correct
11 Incorrect 145 ms 15220 KB Incorrect
12 Halted 0 ms 0 KB -