Submission #1015090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015090		kym	Mouse (info1cup19_mouse)	C++14	42 / 100	98 ms	960 KiB

mouse

#include <bits/stdc++.h>
#ifndef LOCAL
#include <grader.h>
#endif
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = -1;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
#ifdef LOCAL
vector<int>ans;
int sz;
bool good=0;
int query(vector<int> v){
	for(auto x:v)cerr<<x<<" ";
	cerr<<endl;
	if(good)assert(0);
	int res=0;
	for(int i=0;i<=sz-1;i++){
		res+=v[i]==ans[i];
	}
	if(res==sz)good=1;
	return res;
}
#endif
int S;
vector<int>out;
vector<int>aval;
void get(deque<int> vec){ // vec->numbers whose index we still dk
	// try to find the real index of the first guy
	for(auto it=vec.begin();it!=vec.end();){
		if(out[*it]!=-1){
			it=vec.erase(it);
		} else{
			++it;
		}
	}
	if(vec.empty())return;

	vector<int> lftidxes;
	vector<int> qq(S);
	for(int i=0;i<=S-1;i++){
		if(aval[i]==-1)lftidxes.push_back(i);
		else qq[i]=aval[i];
	}
	for(int i=0;i<(int)vec.size();i++){
		qq[lftidxes[i]]=vec[i];
	}

	int oval=query(qq);

	if(oval==S)return;
	vector<int> cands;
	for(int i=1;i<(int)vec.size();i++){
		swap(qq[lftidxes[0]],qq[lftidxes[i]]);
		int qval=query(qq);
		if(qval==S)return;
		swap(qq[lftidxes[0]],qq[lftidxes[i]]);
		if(qval==oval+2){
			out[vec[0]]=lftidxes[i];
			aval[lftidxes[i]]=vec[0];
			out[vec[i]]=lftidxes[0];
			aval[lftidxes[0]]=vec[i];
			get(vec);
			return;
		} else if(qval==oval+1){
			cands.push_back(i);
		}
	}
	if(cands.empty()){ // this means that the vec[0]'s real index is just lftidx[0]
		out[vec[0]]=lftidxes[0];
		aval[lftidxes[0]]=vec[0];
		get(vec);
		return;
	}
	if(cands.size() == 1){
		assert(0);
	}
	if(cands.size() == 2){
		int i0=lftidxes[0];
		int i1=lftidxes[cands[0]];
		int i2=lftidxes[cands[1]];
		int v0=vec[0];
		int v1=vec[cands[0]];
		int v2=vec[cands[1]];

		qq[i2]=v0;
		qq[i1]=v2;
		qq[i0]=v1;
		int qval=query(qq);
		if(qval==S)return;
		if(qval>=oval+2){
			aval[i2]=v0;
			aval[i0]=v1;
			out[v0]=i2;
			out[v1]=i0;
			get(vec);
			return;
		} else{
			aval[i1]=v0;
			aval[i0]=v2;
			out[v0]=i1;
			out[v2]=i0;

			get(vec);
			return;
		}
	}
	assert(0);
}

void solve(int n){
	S=n;
	// let's just try to solve index by index first
	out=vector<int>(S+1,-1);//what is the index of the value
	aval=vector<int>(S+1,-1);//what is the value of the index
	deque<int> vec;
	for(int i=1;i<=S;i++){
		vec.push_back(i);
	}
	for(int i=1;i<vec.size();i++){
		swap(vec[i],vec[rand()%i]);
	}
	get(vec);
}



#ifdef LOCAL
int32_t main() 
{
	srand(42);
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>sz;
	ans=vector<int>(sz);
	for(int i=0;i<=sz-1;i++){
		cin>>ans[i];
	}
	solve(sz);
	cout<<good<<endl;

}
#endif

Compilation message (stderr)

mouse.cpp: In function 'void solve(int)':
mouse.cpp:131:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |  for(int i=1;i<vec.size();i++){
      |              ~^~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 29.000004 / 38
• Subtask 3: 0 / 49