oj.uz

답안 #1067544

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1067544 2024-08-20T19:58:25 Z Ignut 커다란 상품 (IOI17_prize) C++17
20 / 100
 73 ms 1616 KB 
// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> ask(int i);

map<int, vector<int>> mp;
vector<int> Ask(int i) {
	// cout << "ask " << i << '\n';
	if (mp.count(i)) return mp[i];
	vector<int> ans = ask(i);
	mp[i] = ans;
	return ans;
}

int SZ = 1000;

int n;

vector<int> GetVec(int pos) {
	vector<int> res;
	for (int i = pos; i >= max(0, pos - SZ / 2); i --) res.push_back(pos);
	for (int i = pos + 1; i <= min(n - 1, pos + SZ / 2); i ++) res.push_back(pos);
	return res;
}

int find_best(int nn) {
	n = nn;
	int cntB = 0;
	for (int i = 0; i < min(n, SZ); i ++) {
		vector<int> vec = Ask(i);
		if (vec[0] + vec[1] == 0) return i;
		cntB = max(cntB, vec[0] + vec[1]);
	}
	int L = -1;
	for (int i = 0; i < cntB; i ++) {
		int lo = L + 1, hi = n - 1;
		while (lo < hi) {
			int mid = lo + (hi - lo) / 2;
			int val = mid;
			for (int v : GetVec(mid)) {
				vector<int> vec = Ask(v);
				if (vec[0] + vec[1] == 0)
					return v;
				if (vec[0] + vec[1] != cntB) continue;
				val = v; break;
			}
			vector<int> vec = Ask(val);
			if (vec[0] > i)
				hi = mid - 1;
			else
				lo = mid + 1;
		}
		vector<int> vec = Ask(lo);
		if (vec[0] + vec[1] == 0) return lo;
		L = lo;
	}
	// while (L < n - 1) {
	// 	while (lo < hi) {
	// 		int mid = lo + (hi - lo) / 2;
	// 	}	
	// }
	return n - 1;
}

/*
8
3 2 3 1 3 3 2 3
*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 344 KB Output is correct
2 Correct 5 ms 344 KB Output is correct
3 Correct 5 ms 448 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 4 ms 344 KB Output is correct
8 Correct 5 ms 344 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 6 ms 508 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 5 ms 600 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 4 ms 536 KB Output is correct
5 Correct 5 ms 600 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 5 ms 600 KB Output is correct
8 Correct 4 ms 524 KB Output is correct
9 Correct 5 ms 344 KB Output is correct
10 Correct 5 ms 600 KB Output is correct
11 Correct 8 ms 344 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 9 ms 600 KB Output is correct
14 Correct 8 ms 600 KB Output is correct
15 Correct 14 ms 592 KB Output is correct
16 Partially correct 61 ms 1104 KB Partially correct - number of queries: 7379
17 Correct 2 ms 344 KB Output is correct
18 Partially correct 73 ms 1616 KB Partially correct - number of queries: 8492
19 Correct 2 ms 344 KB Output is correct
20 Correct 21 ms 600 KB Output is correct
21 Incorrect 47 ms 856 KB answer is not correct
22 Halted 0 ms 0 KB -