Submission #1318534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318534		muhammad-ahmad	Mouse (info1cup19_mouse)	C++20	0 / 100	27 ms	404 KiB

mouse

#include "grader.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
#include <chrono>
using namespace std;

void fast_io() {
	// freopen("", "r", stdin);
	// freopen("", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	cout << setprecision(9);
}


// #define int long long
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second

// vector<int> y = {1, 4, 2, 5, 3};

int N;
// int query(vector<int> x){
	// int c = 0;
	// for (int i = 0; i < N; i++){
		// if (x[i] == y[i]) c++;
	// }
	// if (c == N) cout << "OK" << endl;
	// return c;
// }

void solve(int n) {
	vector<int> Q;
	N = n;
	for (int i = 1; i <= n; i++) Q.push_back(i);
	if (n <= 3){
		int x = query(Q);
		if (x == n) return;
		while (next_permutation(all(Q))){
			x = query(Q);
			if (x == n) return;
		}
	}
	
	for (int i = 1; i <= 20; i++){
		int x = query(Q);
		if (x == 0) break;
		if (x == n) return;
		random_shuffle(Q.begin(), Q.end());
	}
	int idx[300];
	for (int i = 0; i < n; i++){
		idx[Q[i]] = i;
	}
	
	int v1 = 0, v2 = 0, B = 0;
	for (int i = 0; i < n; i++){
		if (idx[1] == i) continue;
		swap(Q[i], Q[idx[1]]);
		int x = query(Q);
		if (x == n) return;
		swap(Q[i], Q[idx[1]]);
		if (x == 2){
			B = 1;
			v1 = Q[i];
			break;
		}
		if (x == 1){
			if (v1 == 0) v1 = Q[i];
			else v2 = Q[i]; 
		}
	}
	
	bool T[n + 1] = {};
	
	if (B){
		swap(idx[1], idx[v1]);
		swap(Q[idx[1]], Q[idx[v1]]);
		T[1] = T[v1] = 1;
	}
	else {
		swap(Q[idx[1]], Q[idx[v1]]);
		swap(Q[idx[1]], Q[idx[v2]]);
		int x = query(Q);
		if (x == n) return;
		if (x == 0){
			swap(Q[idx[v1]], Q[idx[v2]]);
			swap(Q[idx[v1]], Q[idx[1]]);
			swap(idx[1], idx[v2]);
			swap(idx[v2], idx[v1]);
			x = query(Q);
			if (x == n) return;
			T[1] = T[v1] = 1;
			if (x == 3) T[v2] = 1;
		}
		else{
			T[1] = T[v2] = 1;
			swap(idx[v1], idx[1]);
			swap(idx[v2], idx[v1]);	
			if (x == 3) T[v1] = 1;
		}
	}
// 	

	// for (auto i : Q) cout << i << ' ';
	// cout << endl;
	vector<int> avl, unavl;
	while (1){
		avl.clear();
		unavl.clear();
		for (int i = 1; i <= n; i++){
			if (T[i]) avl.push_back(i);
			else unavl.push_back(i);
		}
		int j = unavl.back();
		if (unavl.empty()){
			query(Q);
			return;
		};
		unavl.pop_back();
		if (unavl.empty()) {
			query(Q);
			return;
		}
		// for (auto i : Q) cout << i << ' ';
		// cout << endl;
		// for (auto k : unavl) cout << k << ' ';
		// cout << endl;
		int x;
		for (auto i : unavl){
			swap(Q[idx[avl[0]]], Q[idx[i]]);
			swap(Q[idx[i]], Q[idx[j]]);
			x = query(Q);
			// for (auto jj : Q) cout << jj << ' ';
			// cout << endl;
			swap(Q[idx[i]], Q[idx[j]]);
			swap(Q[idx[avl[0]]], Q[idx[i]]);
			if (x == (int) avl.size()){
				swap(Q[idx[i]], Q[idx[j]]);
				swap(idx[i], idx[j]);
				T[j] = 1;
				break;
			}
		}
	}
	// for (auto i : Q) cout << i << ' ';
	// cout << "HERE" << endl;
	// cout << endl;
	return;
	
}

// signed main() {
	// fast_io();
	// srand(chrono::steady_clock::now().time_since_epoch().count());
	// int tc = 1;
	// cin >> tc;
	// while (tc--){
		// int N; cin >> N;
		// solve(N);
	// }
	// return 0;
// }
// 

Compilation message (stderr)

mouse.cpp: In function 'void solve(int)':
mouse.cpp:63:31: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   63 |                 random_shuffle(Q.begin(), Q.end());
      |                 ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from grader.h:5,
                 from mouse.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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