oj.uz

Submission #353303

# Submission time Handle Problem Language Result Execution time Memory
353303 2021-01-21T07:17:56 Z arnold518 Nizovi (COI14_nizovi) C++14
60 / 100
 235 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+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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Incorrect 4 ms 364 KB Incorrect
3 Incorrect 4 ms 364 KB Incorrect
4 Incorrect 51 ms 492 KB Incorrect
5 Correct 55 ms 512 KB Output is correct
6 Correct 56 ms 392 KB Output is correct
7 Correct 167 ms 364 KB Output is correct
8 Correct 201 ms 492 KB Output is correct
9 Correct 200 ms 392 KB Output is correct
10 Incorrect 235 ms 396 KB Total cost of reverse commands > 3 000 000