oj.uz

답안 #881250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881250 2023-12-01T01:07:03 Z GusterGoose27 Worm Worries (BOI18_worm) C++17
32 / 100
 2 ms 4440 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6+5;
int n, m, k, q;
int arr[MAXN];

int query(int i) {
	if (i < 0 || i >= n) return 0;
	if (arr[i] == -1) {
		q--;
		assert(q >= 0);
		cout << "? " << i+1 << " 1 1" << endl;
		cin >> arr[i];
	}
	return arr[i];
}

void make_answer(int i) {
	cout << "! " << i+1 << " 1 1\n";
}

int main() {
	cin >> n >> m >> k >> q;
	assert(m == 1); assert(k == 1);
	fill(arr, arr+n, -1);
	int l = -1, r = n;
	while (r > l) {
		if (r-l == 1) {
			if (query(r) > query(l)) l = r;
			else r = l;
		}
		else if (r-l == 2) {
			query(l+1);
			int v = l;
			for (int i = l+1; i <= r; i++) if (query(i) > query(v)) v = i;
			l = r = v;
		}
		else if (r-l == 3) {
			if (query(l) >= query(r)) {
				if (query(l) >= query(l+1)) r = l;
				else if (query(l+1) >= query(l+2)) l = r = l+1;
				else if (query(l+2) >= query(r)) l = r;
			}
			else {
				if (query(r) >= query(r-1)) l = r;
				else if (query(r-1) >= query(r-2)) l = r = r-1;
				else if (query(r-2) >= query(l)) r = l;
			}
		}
		else {
			if (query(l) < query(r)) { // right thing has to be strictly greater
				int i = r-(r-l+2)/3;
				int j = (l+i+1)/2;
				if (query(i) < query(r)) {
					l = i;
				}
				else {
					if (query(i) > query(j)) {
						if (query(i+1) > query(i)) l = i+1;
						else {
							l = j;
							r = i;
						}
					}
					else {
						if (query(j-1) >= query(j)) {
							r = j-1;
						}
						else {
							l = j;
							r = i;
						}
					}
				}
			}
			else { // right thing has to be strictly greater
				int i = l+(r-l+2)/3;
				int j = (r+i)/2;
				if (query(i) <= query(l)) {
					r = i;
				}
				else {
					if (query(i) >= query(j)) {
						if (query(i-1) >= query(i)) r = i-1;
						else {
							l = i;
							r = j;
						}
					}
					else {
						if (query(j+1) > query(j)) {
							l = j+1;
						}
						else {
							l = i;
							r = j;
						}
					}
				}
			}
			//  = (query(l) >= query(r) ?  : r-(r-l+2)/3);
			// int j = (query(l) >= query(r) ? (r+i)/2 : (l+i)/2);
			// if (query(i))
		}
	}
	make_answer(l);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 1 ms 4184 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4436 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4184 KB Output is correct
7 Correct 1 ms 4184 KB Output is correct
8 Correct 1 ms 4184 KB Output is correct
9 Correct 1 ms 4184 KB Output is correct
10 Correct 1 ms 4184 KB Output is correct
11 Correct 1 ms 4184 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 596 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -