Submission #781121

#	Time	Username	Problem	Language	Result	Execution time	Memory
781121		JoenPoenMan	Xylophone (JOI18_xylophone)	C++17	100 / 100	93 ms	724 KiB

xylophone

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

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

#define ALL(arr) begin(arr), end(arr)
#define CONTAINS(arr, val) (find(begin(arr), end(arr), val) != end(arr))

vector<vector<int>> poss;
vector<int> found;
vector<int> foundvals;

int binSearch(int bot, int top, int diff) {
	int mid;
	int low = bot, high = top;
	while (low != high) {
		mid = (low+high)/2;
		int res = high;
		if (mid != high)
			res = query(bot, mid);
		if (res == diff) high = mid;
		else low = mid+1;
	}
	return low;
}


void solve(int N) {
	poss.resize(N+1);
	int n = 1;
	int res = binSearch(1, N, N-1);
	poss[res] = {N};
	found.push_back(res);
    answer(res, N);
	foundvals.push_back(N);
	while (n < N) {
		int tmp = 0;
		for (int iii = 0; iii < found.size(); iii++) {
			int i = found[iii];
			if (i != N && poss[i+1].size() == 0) {
				tmp++;
				int low, high;
				int diff = query(i, i+1);
				low = poss[i][0]-diff, high = poss[i][0]+diff;
				int c = 0;
				if (low >= 1 && !CONTAINS(foundvals, low)) {
					c++;
					poss[i+1].push_back(low);
				}
				if (high <= N && !CONTAINS(foundvals, high)) {
					c++;
					poss[i+1].push_back(high);
				}
				if (c == 1) {
                    answer(i+1, poss[i+1][0]);
					found.push_back(i+1);
					foundvals.push_back(poss[i+1][0]);
					n++;
				}
			}
			if (i != 1 && poss[i-1].size() == 0) {
				tmp++;
				int low, high;
				int diff = query(i-1, i);
				low = poss[i][0]-diff, high = poss[i][0]+diff;
				int c = 0;
				if (low >= 1 && !CONTAINS(foundvals, low)) {
					c++;
					poss[i-1].push_back(low);
				}
				if (high <= N && !CONTAINS(foundvals, high)) {
					c++;
					poss[i-1].push_back(high);
				}
				if (c == 1) {
                    answer(i-1, poss[i-1][0]);
					found.push_back(i-1);
					foundvals.push_back(poss[i-1][0]);
					n++;
				}
			}
		}
		if (!tmp) {
			for (int iii = 0; iii < found.size(); iii++) {
			    int i = found[iii];
				if (i != 1 && i != N && (poss[i-1].size() > 1 ^ poss[i+1].size() > 1)) {
					bool below = poss[i-1].size() > 1;
					int res = query(i-1, i+1);
					int i0 = i + (below ? 1 : -1);
					int i0i = abs(poss[i][0] - poss[i + (below ? 1 : -1)][0]);
					int ii1 = abs(poss[i][0] - poss[i + (below ? -1 : 1)][0]);
					int corr;
					if (res == i0i || ii1 == res) {
						if (poss[i0][0] > poss[i][0]) 
							corr = max(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
						else corr = min(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
						
					}
					else {
						if (poss[i0][0] > poss[i][0]) 
							corr = min(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
						else corr = max(poss[i + (below ? -1 : 1)][0], poss[i + (below ? -1 : 1)][1]);
					}
					poss[i + (below ? -1 : 1)].clear();
					poss[i + (below ? -1 : 1)].push_back(corr);
					foundvals.push_back(corr);
					found.push_back(i + (below ? -1 : 1));
                    answer(i + (below ? -1 : 1), corr);
					n++;
					break;
				}
			}
		}
	}
}

Compilation message (stderr)

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for (int iii = 0; iii < found.size(); iii++) {
      |                     ~~~~^~~~~~~~~~~~~~
xylophone.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (int iii = 0; iii < found.size(); iii++) {
      |                      ~~~~^~~~~~~~~~~~~~
xylophone.cpp:88:47: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   88 |     if (i != 1 && i != N && (poss[i-1].size() > 1 ^ poss[i+1].size() > 1)) {
      |                              ~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53