Submission #1274720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274720		nicolo_010	통행료 (IOI18_highway)	C++20	18 / 100	76 ms	4696 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<int> query;
vector<int> s;
vector<int> u, v;

bool diff() {
	int m = query.size();
	for (int i=0; i<m; i++) {
		query[i] = (s[u[i]] == s[v[i]]);
	}
	ll w = ask(query);
	return (w%2==1);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	int m = U.size();
	u = U, v = V;
	query.assign(m, 0);
	s.assign(N, 0);
	vector<int> grp;
	int xr=0;
	for (int b=0; b<17; b++) {
		for (int i=0; i<N; i++) {
			s[i] = !!(i&(1<<b));
		}
		if (diff()) {
			xr |= (1<<b);
			grp = s;
		}
	}
	int l = 0, r = N-1;
	int ans = 0;
	while (l <= r) {
		int mid = (l+r)/2;
		for (int i=0; i<N; i++) {
			s[i] = (grp[i] && l <= i && i <= mid);
		}
		if (diff()) {
			r = mid-1;
		}
		else {
			l = mid+1;
			ans = mid+1;
		}
	}
	answer(ans, ans^xr);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 18 / 18
• Subtask 6: 0 / 31