| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1318526 | muhammad-ahmad | Mouse (info1cup19_mouse) | C++20 | 0 ms | 0 KiB |
// #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, 3, 2};
int query(vector<int> x){
int c = 0;
for (int i = 0; i < (int) y.size(); i++){
if (x[i] == y[i]) c++;
}
return c;
}
void solve(int n) {
vector<int> Q;
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[8];
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()) return;
unavl.pop_back();
if (unavl.empty()) return;
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;
}
}
break;
}
// for (auto i : Q) cout << i << ' ';
// 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;
}