oj.uz

Submission #200186

# Submission time Handle Problem Language Result Execution time Memory
200186 2020-02-05T15:48:25 Z mohammedehab2002 Mouse (info1cup19_mouse) C++14
90.077 / 100
 162 ms 4120 KB 
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> ans;
map<vector<int>,int> m;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int myquery(vector<int> v,int f=0,int s=0)
{
	vector<int> tmp=ans;
	int pos=0;
	for (int i:v)
	{
		while (tmp[pos])
		pos++;
		tmp[pos]=i;
	}
	swap(tmp[find(tmp.begin(),tmp.end(),f)-tmp.begin()],tmp[find(tmp.begin(),tmp.end(),s)-tmp.begin()]);
	if (!m.count(tmp))
	m[tmp]=query(tmp);
	return m[tmp];
}
int go(int l,int r,vector<int> p)
{
	if (l==r)
	{
		int pos=0;
		for (int i=0;i<=l;i++)
		{
			while (ans[pos])
			pos++;
			if (i==l)
			{
				ans[pos]=p[l];
			}
			pos++;
		}
		return p[l];
	}
	if (l+1==r)
	{
		int t=1;
		while (t==p[l] || t==p[r])
		t++;
		int a=myquery(p,p[l],t);
		if (a==ans.size())
		return -1;
		int b=myquery(p,p[r],t);
		if (b==ans.size())
		return -1;
		if (a<b)
		return go(l,l,p);
		return go(r,r,p);
	}
	int a=myquery(p);
	if (a==ans.size())
	return -1;
	if (l+2==r)
	{
		int b=myquery(p,p[l],p[l+1]);
		if (b==ans.size())
		return -1;
		if (a>b)
		return go(l,l+1,p);
		return go(r,r,p);
	}
	int mid=(l+r)/2;
	for (int t=0;;t^=1)
	{
		vector<int> tmp=p;
		int nl=l,nr=r;
		if (t)
		{
			shuffle(tmp.begin()+l,tmp.begin()+mid+1,rng);
			nr=mid;
		}
		else
		{
			shuffle(tmp.begin()+mid+1,tmp.begin()+r+1,rng);
			nl=mid+1;
		}
		int b=myquery(tmp);
		if (b==ans.size())
		return -1;
		if (a>b)
		return go(nl,nr,p);
		if (a<b)
		return go(nl,nr,tmp);
	}
}
void solve(int n)
{
	ans=vector<int>(n,0);
	vector<int> cur;
	for (int i=1;i<=n;i++)
	cur.push_back(i);
	for (int i=1;i<n;i++)
	{
		while (1)
		{
			shuffle(cur.begin(),cur.end(),rng);
			int a=myquery(cur);
			if (a==ans.size())
			return;
			if (a>=i)
			break;
		}
		int a=go(0,n-i,cur);
		if (a==-1)
		return;
		cur.erase(find(cur.begin(),cur.end(),a));
	}
	myquery(cur);
}

Compilation message

mouse.cpp: In function 'int go(int, int, std::vector<int>)':
mouse.cpp:45:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (a==ans.size())
       ~^~~~~~~~~~~~
mouse.cpp:48:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (b==ans.size())
       ~^~~~~~~~~~~~
mouse.cpp:55:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (a==ans.size())
      ~^~~~~~~~~~~~
mouse.cpp:60:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (b==ans.size())
       ~^~~~~~~~~~~~
mouse.cpp:82:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (b==ans.size())
       ~^~~~~~~~~~~~
mouse.cpp: In function 'void solve(int)':
mouse.cpp:102:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (a==ans.size())
        ~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Correct! Number of queries: 20
2 Correct 5 ms 248 KB Correct! Number of queries: 4
3 Correct 5 ms 376 KB Correct! Number of queries: 17
4 Correct 5 ms 248 KB Correct! Number of queries: 24
5 Correct 5 ms 376 KB Correct! Number of queries: 22
6 Correct 5 ms 376 KB Correct! Number of queries: 19

Subtask #2
35.000014 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Correct! Number of queries: 20
2 Correct 5 ms 248 KB Correct! Number of queries: 4
3 Correct 5 ms 376 KB Correct! Number of queries: 17
4 Correct 5 ms 248 KB Correct! Number of queries: 24
5 Correct 5 ms 376 KB Correct! Number of queries: 22
6 Correct 5 ms 376 KB Correct! Number of queries: 19
7 Correct 10 ms 324 KB Correct! Number of queries: 500
8 Correct 11 ms 380 KB Correct! Number of queries: 400
9 Correct 11 ms 376 KB Correct! Number of queries: 500
10 Correct 12 ms 376 KB Correct! Number of queries: 500
11 Correct 11 ms 376 KB Correct! Number of queries: 400
12 Correct 10 ms 404 KB Correct! Number of queries: 500
13 Correct 11 ms 380 KB Correct! Number of queries: 400
14 Correct 15 ms 504 KB Correct! Number of queries: 500
15 Correct 12 ms 376 KB Correct! Number of queries: 500
16 Correct 12 ms 376 KB Correct! Number of queries: 500

Subtask #3
42.076937 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 252 KB Correct! Number of queries: 20
2 Correct 5 ms 248 KB Correct! Number of queries: 4
3 Correct 5 ms 376 KB Correct! Number of queries: 17
4 Correct 5 ms 248 KB Correct! Number of queries: 24
5 Correct 5 ms 376 KB Correct! Number of queries: 22
6 Correct 5 ms 376 KB Correct! Number of queries: 19
7 Correct 10 ms 324 KB Correct! Number of queries: 500
8 Correct 11 ms 380 KB Correct! Number of queries: 400
9 Correct 11 ms 376 KB Correct! Number of queries: 500
10 Correct 12 ms 376 KB Correct! Number of queries: 500
11 Correct 11 ms 376 KB Correct! Number of queries: 400
12 Correct 10 ms 404 KB Correct! Number of queries: 500
13 Correct 11 ms 380 KB Correct! Number of queries: 400
14 Correct 15 ms 504 KB Correct! Number of queries: 500
15 Correct 12 ms 376 KB Correct! Number of queries: 500
16 Correct 12 ms 376 KB Correct! Number of queries: 500
17 Correct 156 ms 3804 KB Correct! Number of queries: 3200
18 Correct 137 ms 3576 KB Correct! Number of queries: 3100
19 Correct 127 ms 3448 KB Correct! Number of queries: 3100
20 Correct 144 ms 3960 KB Correct! Number of queries: 3300
21 Correct 131 ms 3744 KB Correct! Number of queries: 3200
22 Correct 127 ms 3576 KB Correct! Number of queries: 3100
23 Correct 137 ms 3704 KB Correct! Number of queries: 3200
24 Correct 140 ms 4120 KB Correct! Number of queries: 3300
25 Correct 136 ms 3788 KB Correct! Number of queries: 3300
26 Correct 162 ms 3832 KB Correct! Number of queries: 3300