Submission #295217

#	Time	Username	Problem	Language	Result	Execution time	Memory
295217		Saboon	Highway Tolls (IOI18_highway)	C++17	51 / 100	323 ms	8312 KiB

highway

// Sub 1 2 3 4
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 90000 + 10;
int n;
ll Cost = 0, Step;
vector<int> Q;
vector<int> g[maxn];

int find(vector<int> S){
	assert((int)S.size() > 0);
	int n = S.size();
	int lo = -1, hi = n;
	while (hi - lo > 1){
		int mid = (lo+hi) >> 1;
		for (int itV = 0; itV <= mid; itV++){
			int v = S[itV];
			for (auto idx : g[v])
				Q[idx] ^= 1;
		}
		ll Now = ask(Q);
		for (int itV = 0; itV <= mid; itV++){
			int v = S[itV];
			for (auto idx : g[v])
				Q[idx] ^= 1;
		}
		ll Dif = (Now-Cost)/Step;
		if (Dif & 1)
			hi = mid;
		else
			lo = mid;
	}
	return S[hi];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	Step = B-A;	
	n = N;
	int m = U.size();
	Q.resize(m);
	for (int i = 0; i < m; i++){
		Q[i] = 0;
		g[V[i]].push_back(i);
		g[U[i]].push_back(i);
	}
	Cost = ask(Q);
	vector<int> S, T;
	for (int i = 16; i >= 0; i--){
		for (int v = 0; v < n; v++)
			if (v & (1 << i))
				for (auto idx : g[v])
					Q[idx] ^= 1;
		ll Now = ask(Q);
		for (int v = 0; v < n; v++)
			if (v & (1 << i))
				for (auto idx : g[v])
					Q[idx] ^= 1;
		ll Dif = (Now-Cost)/Step;
		if (Dif & 1){
			for (int v = 0; v < n; v++)
				if (v & (1 << i))
					S.push_back(v);
				else
					T.push_back(v);
			break;
		}
	}
	int s = find(S), t = find(T);
	answer(s,t);
}

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