제출 #286644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
286644		AlanChen	통행료 (IOI18_highway)	C++14	51 / 100	221 ms	3932 KiB

highway

#include "highway.h"



#include <bits/stdc++.h>
using namespace std;

template<class A> using v=vector<A>;

typedef v<int> vi;
typedef long long ll;

#define sz(S) (int)(S).size()
#define pb push_back



#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)


#define trv(x,S) for(auto& x:(S))


const int mx=200100;
int n,m;
int slct[mx];

void find_pair(int N, vi U, vi V, int A, int B)
{
	n=N;
	m=sz(U);
	vi w(m);
	lp(i,m) w[i]=0;
	ll ans1=ask(w);
	ll ans2;
	do
	{
		lp(i,n) slct[i]=rand()%2;
		lp(i,m) w[i]=(slct[U[i]]!=slct[V[i]]);
		ans2=ask(w);
	}
	while(((ans2-ans1)/(B-A))%2==0);

	vi sides[2];
	lp(i,n) sides[slct[i]].pb(i);

	lp(dim,2)
	{
		while(sz(sides[dim])>1)
		{
			int md=sz(sides[dim])/2;
			lp(i,n) slct[i]=0;
			lp(i,md) slct[sides[dim][i]]=true;
			lp(i,m) w[i]=(slct[U[i]]!=slct[V[i]]);
			ans2=ask(w);
			if(((ans2-ans1)/(B-A))%2==0) sides[dim].erase(sides[dim].begin(),sides[dim].begin()+md);
			else sides[dim].resize(md);
		}
	}

	answer(sides[0][0],sides[1][0]);
}

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