oj.uz

Submission #763371

# Submission time Handle Problem Language Result Execution time Memory
763371 2023-06-22T08:39:02 Z vjudge1 Xylophone (JOI18_xylophone) C++17
0 / 100
 59 ms 208 KB 
#include <bits/stdc++.h>
#include "xylophone.h"

const int maxn = 5e3 + 5;

bool check[maxn];

std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());

int randint(int l, int r){
	assert(l <= r);
	return std::uniform_int_distribution<int>(l, r)(rd);
}

void solve(int N){
	int l = 1;
	int r = N;
	while(l < r){
		int mid = (l + r) >> 1;
		int res = query(1, mid);
		if(res != N - 1){
			l = mid + 1;
		}else{
			r = mid;
		}
	}

	int posr = l;

	answer(posr, N);
	check[N] = true;

	l = 1, r = N;
	while(l < r - 1){
		int mid = (l + r) >> 1;
		int res = query(mid, N);
		if(res != N - 1){
			r = mid - 1;
		}else{
			l = mid;
		}
	}

	int posl = l;

	if(query(r, N) == N - 1) posl = r;

	answer(posl, 1);
	check[1] = true;


	int ptr1 = posl - 1, ptr2 = posl + 1, ptr3 = posr + 1;
	int cur1 = 1, cur2 = 1, cur3 = N;
	int cnt = 2;

	while(cnt < N){
		int type = randint(1, 3);
		if(type == 1 && ptr1 >= 1){
			int diff = query(ptr1, ptr1 + 1);
			int waifu1 = cur1 + diff;
			int waifu2 = cur1 - diff;
			if(waifu2 <= 0 || check[waifu2]){
				answer(ptr1, waifu1);
				check[waifu1] = true;
				cur1 = waifu1;
				ptr1--;
				cnt++;
			}else if(waifu1 > N || check[waifu1]){
				answer(ptr1, waifu2);
				check[waifu2] = true;
				cur1 = waifu2;
				ptr1--;
				cnt++;
			}
		}else if(type == 2 && ptr2 >= posl && ptr2 < posr){
			int diff = query(ptr2 - 1, ptr2);
			int waifu1 = cur2 + diff;
			int waifu2 = cur2 - diff;
			if(waifu2 <= 0 || check[waifu2]){
				answer(ptr2, waifu1);
				check[waifu1] = true;
				cur2 = waifu1;
				ptr2++;
				cnt++;
			}else if(waifu1 > N || check[waifu1]){
				answer(ptr2, waifu2);
				check[waifu2] = true;
				cur2 = waifu2;
				ptr2++;
				cnt++;
			}
		}else if(type == 3 && ptr3 <= N){
			int diff = query(ptr3 - 1, ptr3);
			int waifu1 = cur3 + diff;
			int waifu2 = cur3 - diff;
			if(waifu2 <= 0 || check[waifu2]){
				answer(ptr3, waifu1);
				check[waifu1] = true;
				cur3 = waifu1;
				ptr3++;
				cnt++;
			}else if(waifu1 > N || check[waifu1]){
				answer(ptr3, waifu2);
				check[waifu2] = true;
				cur3 = waifu2;
				ptr3++;
				cnt++;
			}
		}
	}

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 59 ms 208 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 59 ms 208 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Incorrect 59 ms 208 KB Wrong Answer [2]
4 Halted 0 ms 0 KB -