Submission #295361

#	Time	Username	Problem	Language	Result	Execution time	Memory
295361		Saboon	통행료 (IOI18_highway)	C++17	18 / 100	321 ms	9048 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, MinP;
vector<int> Q;
vector<int> g[maxn];
int A, B;

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);
	for (int a = 0; 1LL*a*A <= Now and a <= n-1; a += 2)
		if ((Now-1LL*a*A)%B == 0 and a + (Now-1LL*a*A)/B >= MinP)
			return false;
	return true;
}

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 G = gcd(A,B);
	A /= G, B /= G;
	int sub;
	if (U.size() == N-1) // Subtask 1,2,3,4
		sub = 4;
	else if ((A^B)&1)
		sub = 5;
	sub = 6;
	Step = B-A;	
	n = N, ::A = A, ::B = B;
	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);
	MinP = Cost/B;
	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:42:6: warning: unused variable 'Dif' [-Wunused-variable]
   42 |   ll Dif = (Now-Cost)/Step;
      |      ^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:55:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |  if (U.size() == N-1) // Subtask 1,2,3,4
      |      ~~~~~~~~~^~~~~~

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