Submission #200186

#	Time	Username	Problem	Language	Result	Execution time	Memory
200186		mohammedehab2002	Mouse (info1cup19_mouse)	C++14	90.08 / 100	162 ms	4120 KiB

mouse

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

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 / 13
• Subtask 2: 35.000014 / 38
• Subtask 3: 42.076937 / 49