oj.uz

Submission #353345

# Submission time Handle Problem Language Result Execution time Memory
353345 2021-01-21T07:22:37 Z arnold518 Nizovi (COI14_nizovi) C++14
100 / 100
 223 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1000;
const int MAXM = 1e6;
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
 
int N, M;
int B[MAXN+MAXM+10];
 
int cmp(int x, int y)
{
	printf("cmp %d %d\n", x, y);
	fflush(stdout);
	int t;
	scanf("%d", &t);
	//if(B[x]<B[y]) t=-1;
	//if(B[x]==B[y]) t=0;
	//if(B[x]>B[y]) t=1;
	return t;
}
 
void rev(int l, int r)
{
	if(l>r) return;
	if(l==r) return;
	printf("reverse %d %d\n", l, r);
	fflush(stdout);
	//reverse(B+l, B+r+1);
}
 
void end()
{
	printf("end\n");
	fflush(stdout);
	//for(int i=1; i<=N+M; i++) printf("%d ", B[i]); printf("\n");
}
 
pii A[MAXN+10];
 
int main()
{
	scanf("%d%d", &N, &M);
	/*
	for(int i=1; i<=N+M; i++)
	{
		//scanf("%d", &B[i]);
		B[i]=rand(-10, 10);
	}
	sort(B+1, B+N+1);
	sort(B+N+1, B+N+M+1);
	for(int i=1; i<=N+M; i++) printf("%d ", B[i]); printf("\n");
	*/
 
	int bef=N;
	for(int i=1; i<=N; i++)
	{
		int lo=N, hi=N+M+1;
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(cmp(i, mid)==1) lo=mid;
			else hi=mid;
		}
		A[i]={bef, lo};
		bef=lo;
	}
 
	//for(int i=1; i<=N; i++) printf("!%d %d\n", A[i].first, A[i].second);
 
	int s=1;
	for(int i=1; i<=N; i++)
	{
		if(A[i].first==A[i].second)
		{
			s++; continue;
		}
		rev(s, s+N-i);
		rev(s, A[i].second);
		rev(s, s+A[i].second-A[i].first-1);
		s+=A[i].second-A[i].first+1;
	}
	end();
}

Compilation message

nizovi.cpp: In function 'int main()':
nizovi.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |    int mid=lo+hi>>1;
      |            ~~^~~
nizovi.cpp: In function 'int cmp(int, int)':
nizovi.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d", &t);
      |  ~~~~~^~~~~~~~~~
nizovi.cpp: In function 'int main()':
nizovi.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 55 ms 364 KB Output is correct
5 Correct 39 ms 364 KB Output is correct
6 Correct 38 ms 392 KB Output is correct
7 Correct 203 ms 492 KB Output is correct
8 Correct 223 ms 396 KB Output is correct
9 Correct 213 ms 400 KB Output is correct
10 Correct 223 ms 364 KB Output is correct