제출 #139413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
139413		Lawliet	Highway Tolls (IOI18_highway)	C++14	0 / 100	20 ms	2516 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

#define MAX 90010

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

int N, A, B;

int v[MAX];

vector<int> indEdge;

map<pii,int> edges;

/*int ask(vector<int> p)
{
	for(int g = 0 ; g < N - 1 ; g++)
		printf("%d ",p[g]);

	int a;
	scanf("%d",&a);

	return a;
}

void answer(int i, int j)
{
	printf("========= %d %d\n",i,j);
}*/

void find_pair(int n, vector<int> U, vector<int> V, int a, int b)
{
	N = n; A = a; B = b;

	for(int g = 0 ; g < N - 1 ; g++)
	{
		int i = U[g];
		int j = V[g];

		edges[ {i , j} ] = g;
		edges[ {j , i} ] = g;
	}

	for(int g = 1 ; g < N ; g++)
		indEdge.push_back( edges[{g , g - 1}] );

	vector<int> question;

	for(int g = 0 ; g < n - 1 ; g++)
		question.push_back( 0 );

	lli distA = ask( question );

	lli qtdEdges = distA/A;

	lli distB = qtdEdges*B;

	int l = 0, r = n - 2;

	while( l < r )
	{
		int m = (l + r)/2;

		for(int g = 0 ; g < n - 1 ; g++)
			question[ g ] = 0;

		for(int g = l ; g <= m ; g++)
			question[ indEdge[g] ] = 1;

		lli aux = ask( question );

		if(aux == distA) l = m + 1;
		else if(aux == distB) r = m;
		else
		{
			lli other = aux - distA;

			lli qtdOther = other/(B - A);

			//printf("other = %d     %d       %d         m = %d\n",other,qtdOther,qtdEdges,m);

			answer( (m + 1) - qtdOther , qtdEdges + qtdOther - m - 1);

			//printf("ACHEI %d %d\n",(m + 1) - qtdOther,(m + 1) + qtdEdges - qtdOther);
			break;
		}
	}

	//printf("oii %d %d\n",l,l+ 1);
	answer(l , l + 1);

}

/*int main()
{
	int nn, aa, bb;
	scanf("%d %d %d",&nn,&aa,&bb);

	vector<int> uu(nn), vv(nn);

	for(int g = 0 ; g < nn - 1 ; g++)
		scanf("%d %d",&uu[g],&vv[g]);

	find_pair(nn , uu , vv , aa , bb);
}*/

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