Submission #654633

# Submission time Handle Problem Language Result Execution time Memory
654633 2022-11-01T03:22:56 Z mousey Library (JOI18_library) C++17
100 / 100
329 ms 584 KB
#include <bits/stdc++.h>
#include "library.h"
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define vi vector <int>
#define vip vector <pair <int, int> >
#define db double
#define ld long double
#define pdb pair <double, double> 
#define YES cout<<"YES"
#define NO cout<<"NO"
#define nl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll> 
#define pi pair <int, int>
#define pb push_back
#define f first
#define s second
using namespace std;

const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const int MAX_N=1000;

void Solve(int N)
{
	vi ans, v;
	if(N==1)
	{
		ans.pb(1);
		Answer(ans);
		return;	
	}
	for(int i = 1; i <= N; i++) v.pb(1);
	for(int i = 1; i <= N; i++)
	{
		if(i==1) v[0]=0;
		else v[i-1]=0, v[i-2]=1;
		int report=Query(v);
		if(report==1)
		{
			ans.pb(i);
			break;
		}
	}
	for(int i = 2; i <= N; i++)
	{
		vi cur=v;
		int num=N-i+1;
//		printf("%d\n", num);
//		for(auto i: cur)
//		{
//			printf("%d ", i);
//		}
//		printf("\n");
//		fflush(stdout);
		while(num>1)
		{
			vi a, b;
			int cnt=0;
			for(auto j: cur)
			{
				if(cnt<num/2)
				{
					a.pb(j);
					if(j==1) cnt++;
					b.pb(0);
				}
				else
				{
					b.pb(j);
					a.pb(0);
				}
			}
			int report1=Query(a);
			a[ans[i-2]-1]=1;
			int report2=Query(a);
			a[ans[i-2]-1]=0;
//			printf("array a: ");
//			for(auto i: a) printf("%d ", i);
//			printf("\narray b: ");
//			for(auto i: b) printf("%d ", i);
//			printf("\n");
			if(report1==report2) cur=a, num=cnt;
			else cur=b, num-=cnt;
		}
		for(int i = 0; i < N; i++)
		{
			if(cur[i]==1) ans.pb(i+1), v[i]=0;
		}
//		printf("\n");
	}
//	printf("\n");
//	for(auto i: ans)
//	{
//		printf("%d ", i);
//	}
	Answer(ans);
}
/*
5
4 2 5 3 1
*/
# Verdict Execution time Memory Grader output
1 Correct 33 ms 208 KB # of queries: 2375
2 Correct 36 ms 208 KB # of queries: 2409
3 Correct 33 ms 208 KB # of queries: 2648
4 Correct 39 ms 208 KB # of queries: 2595
5 Correct 38 ms 208 KB # of queries: 2508
6 Correct 39 ms 208 KB # of queries: 2551
7 Correct 36 ms 208 KB # of queries: 2544
8 Correct 32 ms 208 KB # of queries: 2420
9 Correct 30 ms 208 KB # of queries: 2546
10 Correct 22 ms 304 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 77
16 Correct 3 ms 208 KB # of queries: 183
# Verdict Execution time Memory Grader output
1 Correct 33 ms 208 KB # of queries: 2375
2 Correct 36 ms 208 KB # of queries: 2409
3 Correct 33 ms 208 KB # of queries: 2648
4 Correct 39 ms 208 KB # of queries: 2595
5 Correct 38 ms 208 KB # of queries: 2508
6 Correct 39 ms 208 KB # of queries: 2551
7 Correct 36 ms 208 KB # of queries: 2544
8 Correct 32 ms 208 KB # of queries: 2420
9 Correct 30 ms 208 KB # of queries: 2546
10 Correct 22 ms 304 KB # of queries: 1474
11 Correct 0 ms 208 KB # of queries: 0
12 Correct 0 ms 208 KB # of queries: 1
13 Correct 0 ms 208 KB # of queries: 4
14 Correct 1 ms 208 KB # of queries: 7
15 Correct 1 ms 208 KB # of queries: 77
16 Correct 3 ms 208 KB # of queries: 183
17 Correct 294 ms 416 KB # of queries: 17982
18 Correct 281 ms 584 KB # of queries: 17293
19 Correct 292 ms 328 KB # of queries: 17467
20 Correct 284 ms 304 KB # of queries: 16325
21 Correct 252 ms 304 KB # of queries: 15324
22 Correct 329 ms 316 KB # of queries: 17669
23 Correct 294 ms 312 KB # of queries: 17224
24 Correct 135 ms 316 KB # of queries: 7915
25 Correct 316 ms 304 KB # of queries: 17136
26 Correct 249 ms 328 KB # of queries: 15963
27 Correct 126 ms 208 KB # of queries: 8040
28 Correct 329 ms 304 KB # of queries: 15957
29 Correct 279 ms 312 KB # of queries: 15939
30 Correct 268 ms 304 KB # of queries: 15957