제출 #1319086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319086		Jawad_Akbar_JJ	Mouse (info1cup19_mouse)	C++20	36.67 / 100	61 ms	420 KiB

mouse

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>
#include "grader.h"

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 500;
int seen[N], p[N], num;

int ask(vector<int> v, int i, int j){
	num++;
	// if (num > 20)
	// 	exit(0);
	swap(v[i], v[j]);
	i = query(v);
	if (i == v.size())
		exit(0);
	return query(v);
}

void solve(int n){
	vector<int> ind, val;
	for (int i=0;i<n;i++){
		ind.push_back(i);
		val.push_back(i+1);
	}

	// shuffle(begin(val), end(val), rnd);
	int cur = ask(val, 1, 1);

	while (cur < n){
		// cout<<cur<<endl;
		while (ind.size() > 0 and seen[ind[0]])
			ind.erase(begin(ind));
		for (int i=1;i<ind.size();i++){
			if (seen[ind[0]] or seen[ind[i]])
				continue;

			int cur1 = ask(val, ind[0], ind[i]);
			if (cur1 == cur)
				continue;
			
			if (cur1 == cur - 2){
				seen[ind[0]] = seen[ind[i]] = 1;
			}
			else if (cur1 == cur + 2){
				seen[ind[0]] = seen[ind[i]] = 1;
				swap(val[ind[0]], val[ind[i]]);
				cur += 2;
			}
			else if (cur1 == cur - 1){
				int j = 0;
				if (ind[0] == j or ind[i] == j)
					j++;
				if (ind[0] == j or ind[i] == j)
					j++;
				if (seen[j]){
					if (ask(val, ind[0], j) == cur - 2)
						seen[ind[0]] = 1;
					else
						seen[ind[i]] = 1;
				}
				else{
					int cur2 = ask(val, ind[0], j), cur3 = ask(val, ind[i], j);
					if (cur2 == cur or cur2 == cur - 1 and cur3 == cur - 2)
						seen[ind[i]] = 1;
					else
						seen[ind[0]] = 1;
				}
			}
			else{
				swap(val[ind[0]], val[ind[i]]);
				cur++, i--;
			}
		}
		if (seen[ind[0]] == 0)
			return;
	}
}

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