Submission #353303

#	Time	Username	Problem	Language	Result	Execution time	Memory
353303		arnold518	Nizovi (COI14_nizovi)	C++14	60 / 100	235 ms	512 KiB

nizovi

#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+1, 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 (stderr)

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: 60 / 100