oj.uz

Submission #286644

# Submission time Handle Problem Language Result Execution time Memory
286644 2020-08-30T15:59:24 Z AlanChen Highway Tolls (IOI18_highway) C++14
51 / 100
 221 ms 3932 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 380 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 16 ms 640 KB Output is correct
3 Correct 114 ms 3056 KB Output is correct
4 Correct 115 ms 2984 KB Output is correct
5 Correct 163 ms 3044 KB Output is correct
6 Correct 153 ms 3056 KB Output is correct
7 Correct 152 ms 3048 KB Output is correct
8 Correct 107 ms 3052 KB Output is correct
9 Correct 111 ms 3096 KB Output is correct
10 Correct 108 ms 3180 KB Output is correct
11 Correct 113 ms 2992 KB Output is correct
12 Correct 111 ms 3044 KB Output is correct
13 Correct 117 ms 3128 KB Output is correct
14 Correct 165 ms 2992 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 33 ms 888 KB Output is correct
3 Correct 35 ms 1272 KB Output is correct
4 Correct 104 ms 2984 KB Output is correct
5 Correct 109 ms 3060 KB Output is correct
6 Correct 153 ms 3020 KB Output is correct
7 Correct 108 ms 3048 KB Output is correct
8 Correct 102 ms 2916 KB Output is correct
9 Correct 157 ms 3116 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 12 ms 640 KB Output is correct
3 Correct 129 ms 2600 KB Output is correct
4 Correct 156 ms 3048 KB Output is correct
5 Correct 130 ms 3056 KB Output is correct
6 Correct 153 ms 3056 KB Output is correct
7 Correct 157 ms 3132 KB Output is correct
8 Correct 155 ms 3056 KB Output is correct
9 Correct 155 ms 2988 KB Output is correct
10 Correct 158 ms 3056 KB Output is correct
11 Correct 153 ms 3052 KB Output is correct
12 Correct 153 ms 3252 KB Output is correct
13 Correct 161 ms 3048 KB Output is correct
14 Correct 151 ms 3060 KB Output is correct
15 Correct 112 ms 3048 KB Output is correct
16 Correct 149 ms 3052 KB Output is correct
17 Correct 149 ms 3056 KB Output is correct
18 Correct 113 ms 3132 KB Output is correct
19 Correct 107 ms 3048 KB Output is correct
20 Correct 132 ms 3056 KB Output is correct
21 Correct 161 ms 2992 KB Output is correct
22 Correct 104 ms 3016 KB Output is correct
23 Correct 156 ms 3152 KB Output is correct
24 Correct 112 ms 3052 KB Output is correct
25 Correct 115 ms 3084 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 640 KB Output is correct
2 Incorrect 15 ms 760 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 640 KB Output is correct
2 Correct 19 ms 632 KB Output is correct
3 Correct 176 ms 3204 KB Output is correct
4 Correct 186 ms 3304 KB Output is correct
5 Correct 159 ms 3424 KB Output is correct
6 Correct 221 ms 3932 KB Output is correct
7 Correct 123 ms 3356 KB Output is correct
8 Incorrect 128 ms 3368 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -