Submission #295236

#	Time	Username	Problem	Language	Result	Execution time	Memory
295236		Saboon	Highway Tolls (IOI18_highway)	C++17	69 / 100	378 ms	8984 KiB

highway

#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];

bool isOdd(ll Cost, ll Now, int sub){
	if (sub <= 4){
		ll T = abs(Now-Cost);
		return (T/Step)&1;
	}
	if (sub == 5)
		return (Now&1);
}

int find(vector<int> S, int sub){
	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 (isOdd(Cost, Now, sub))
			hi = mid;
		else
			lo = mid;
	}
	return S[hi];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
	int sub = 1;
	if (U.size() == N-1) // Subtask 1,2,3,4
		sub = 4;
	else if ((A^B)&1)
		sub = 5;
	Step = B-A;	
	n = N;
	int m = U.size();
	Q.resize(m);
	for (int i = 0; i < m; i++){
		Q[i] = 1;
		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;
		if (isOdd(Cost, Now, sub)){
			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, sub), t = find(T, sub);
	answer(s,t);
}

Compilation message (stderr)

highway.cpp: In function 'int find(std::vector<int>, int)':
highway.cpp:37:6: warning: unused variable 'Dif' [-Wunused-variable]
   37 |   ll Dif = (Now-Cost)/Step;
      |      ^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:48:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |  if (U.size() == N-1) // Subtask 1,2,3,4
      |      ~~~~~~~~~^~~~~~
highway.cpp: In function 'bool isOdd(ll, ll, int)':
highway.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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