Submission #139403

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
139403	2019-07-31T16:09:33 Z	Kenzo_1114	Highway Tolls (IOI18_highway)	C++14	6 / 100	231 ms	2308 KB

highway

#include<bits/stdc++.h>
#include "highway.h"
using namespace std;
const int MAXN=200010;

/*
long long int ask(vector<int> aux)
{
	printf("ASK : ");
	for(int i=0;i<aux.size();i++)	printf("%d",aux[i]);
	printf("\n");
	
	long long int val;
	scanf("%lld",&val);
	return val;
}
*/

void find_pair(int n,vector<int> u,vector<int> v,int a,int b)
{
	vector<int> w;
	
	for(int i=0;i<u.size();i++)	w.push_back(0);
	
	long long int dist=0;
	dist=ask(w);
//	printf("dist = %lld\n",dist);
	
	int ini=0,	fim=u.size()-1;
	while(ini<fim)
	{
		int mid=(ini==fim-1) ? ini : (ini+fim)/2;
//		printf("ini = %d  fim = %d  mid = %d\n",ini,fim,mid);
		
		w.clear();
		for(int i=0;i<ini;i++)	w.push_back(0);
		for(int i=ini;i<=mid;i++)	w.push_back(1);
		for(int i=mid+1;i<u.size();i++)	w.push_back(0);
		
		if(ask(w)>dist)	fim=mid;
		else	ini=mid+1;
	}
	
	answer(ini,ini+dist/a);
}

/*
int main ()
{
	int m,n,a,b;
	vector<int> u,v;
	
	scanf("%d %d",&n,&m);
	
	for(int i=0;i<m;i++)
		scanf("%d %d",&a,&b),	u.push_back(a),	v.push_back(b);
		
	scanf("%d %d",&a,&b);	
	
	find_pair(n,u,v,a,b);

}
*/
/*
7 6
0 1
1 2
2 3
3 4
4 5
5 6
1 10000

*/

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<u.size();i++) w.push_back(0);
              ~^~~~~~~~~
highway.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=mid+1;i<u.size();i++) w.push_back(0);
                   ~^~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	376 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	248 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	520 KB	Output is correct
2	Correct	54 ms	724 KB	Output is correct
3	Correct	47 ms	928 KB	Output is correct
4	Correct	231 ms	2300 KB	Output is correct
5	Correct	228 ms	2308 KB	Output is correct
6	Correct	136 ms	2308 KB	Output is correct
7	Correct	131 ms	2304 KB	Output is correct
8	Correct	114 ms	2308 KB	Output is correct
9	Correct	135 ms	2300 KB	Output is correct