oj.uz

Submission #780736

# Submission time Handle Problem Language Result Execution time Memory
780736 2023-07-12T12:28:51 Z JoenPoenMan Xylophone (JOI18_xylophone) C++17
0 / 100
 0 ms 208 KB 

#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ii;

vector<ii> locations;

void findNext2(int N, int top, int bot, int prevLoc, bool gr1);

void findNext1(int N, int top, int bot = 1, int prevLoc = 1, bool gr1 = false, bool exl = false) {
	if (top == bot) return;
	int mid;
	int low = bot, high = top;
	int prev = query(low, high);
	if (abs(top - bot) != 1) {
		while (low != high) {
			mid = (low+high)/2;
			int res = query(bot, mid);
			if (res == prev) high = mid;
			else low = mid+1;
		}
	} else low = top;
	locations.push_back({prevLoc+prev*(gr1?-1:1), low});
	findNext1(N, top, low, prevLoc+prev*(gr1?-1:1), !gr1, true);
	findNext2(N, low, bot + exl, prevLoc+prev*(gr1?-1:1), !gr1);
}

void findNext2(int N, int top, int bot, int prevLoc = 1, bool gr1 = false ) {
	if (top == bot) return;
	int mid;
	int low = bot, high = top;
	int prev = query(low, high);
	if (abs(top - bot) != 1) {
		while (low != high) {
			mid = (low+high+1)/2;
			int res = query(mid, top);
			if (res == prev) low = mid;
			else high = mid-1;
		}
	} else low = bot;
	locations.push_back({prevLoc+prev*(gr1?-1:1), low});
	findNext1(N, top-1, low, prevLoc+prev*(gr1?-1:1), !gr1, true);
	findNext2(N, low, bot, prevLoc+prev*(gr1?-1:1), !gr1);
}

void solve(int N) {
	findNext1(N, N);
	for (int i = 0; i < N; i++) {
		answer(locations[i].second, i+1);
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -