Submission #414083

#	Time	Username	Problem	Language	Result	Execution time	Memory
414083		jamezzz	Mouse (info1cup19_mouse)	C++14	0 / 100	1 ms	200 KiB

mouse

#include "grader.h"

#include <bits/stdc++.h>
using namespace std;

#define pf printf

vector<int> todo,v;

int check(int x){ //swap (0,1),(2,3)...(2*x,2*x+1)
	for(int i=0;i<=x;++i){
		swap(v[todo[2*i]],v[todo[2*i+1]]);
	}
	int res=query(v);
	for(int i=0;i<=x;++i){
		swap(v[todo[2*i]],v[todo[2*i+1]]);
	}
	return res;
}

void solve(int N) {
    for(int i=1;i<=N;++i)v.push_back(i);
    while(true){
		int res=query(v);
		if(res==N)return;
		if(res==0)break;
		random_shuffle(v.begin(),v.end());
	}
    for(int i=0;i<N;++i)todo.push_back(i);
    random_shuffle(todo.begin(),todo.end());
    int pv=0;
    while(!todo.empty()){
		if(check(todo.size()/2-1)==pv){
			random_shuffle(todo.begin(),todo.end());
			continue;
		}
		int lo=0,hi=todo.size()/2-1,mid,res,val;
		while(lo<=hi){
			mid=(lo+hi)/2;
			int tmp=check(mid);
			if(tmp==N)return;
			if(tmp>pv){
				res=mid;
				val=tmp;
				hi=mid-1;
			}
			else lo=mid+1;
		}
		if(val==pv+2){
			swap(v[todo[2*res]],v[todo[2*res+1]]);
			todo.erase(todo.begin()+2*res,todo.begin()+2*res+2);
		}
		else{
			swap(v[todo[2*res]],v[todo[2*res+1]]);
			int o=(2*res+2<todo.size())?2*res+2:2*res-1;
			swap(v[todo[2*res]],v[todo[o]]);
			int tmp=query(v);
			if(tmp==N)return;
			swap(v[todo[2*res]],v[todo[o]]);
			if(tmp>pv){
				todo.erase(todo.begin()+2*res+1);
			}
			else todo.erase(todo.begin()+2*res);
		}
		pv=query(v);
		if(pv==N)return;
	}
	return;
}

Compilation message (stderr)

mouse.cpp: In function 'void solve(int)':
mouse.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    int o=(2*res+2<todo.size())?2*res+2:2*res-1;
      |           ~~~~~~~^~~~~~~~~~~~
mouse.cpp:49:3: warning: 'val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |   if(val==pv+2){
      |   ^~
mouse.cpp:50:32: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |    swap(v[todo[2*res]],v[todo[2*res+1]]);
      |                               ~^~~~

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