| 18386 | 2025-10-21 14:58:10 | ubormaci | Találd ki a permutációt! | cpp17 | Time limit exceeded 0/100 | 1ms | 748 KiB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cstdint>
#include <bitset>
using namespace std;
typedef int32_t ll;
ll ask(ll i, ll j) {
cout << i << " " << j << "\n";
cout.flush();
ll x;
cin >> x;
if(x == -100) {
exit(0);
}
return x;
}
vector<ll> solve(ll size) {
ll n = size;
vector<bitset<12>> v(n+1, bitset<12>(0));
/*
v[0][1] = 1;
cerr << v[0] << "\n";
for(ll i = 0; i < v[0].size(); i++) {
cout << v[0][i];
}
return vector<int>(n, 0);
*/
vector<ll> out(n+1, 0);
vector<ll> largestbit(n+1, 0);
vector<ll> characteristic(11, 0);
// we can match each index with itself to get its highest bit
ll hg = 0;
for(ll i = 1; i <= n; i++) {
//cerr << "\ni=" << i;
ll curr = ask(i, i);
//cerr << "\ncurr=" << curr;
v[i][curr] = 1;
largestbit[i] = curr;
hg = max(hg, curr);
characteristic[curr] = i;
}
//cerr << "\nhg=" << hg;
for(ll i = 0; i < hg; i++) {
//cerr << "\ni=" << i;
ll base = characteristic[i];
if(base == 0) {
continue;
}
//cerr << "\ncharacteristic=" << base;
for(ll j = 1; j <= n; j++) {
//cerr << "\nj=" << j;
if(largestbit[j] <= largestbit[base]) {
//cerr << "\nlargest bit of j is smaller or equal to base's";
continue;
}
ll iscurr = ask(base, j);
//cerr << "\niscurr(base,j)=" << iscurr;
if(iscurr == i) {
v[j][i] = 1;
}
}
}
vector<ll> twopows(12, 0);
ll r = 1;
for(ll i = 0; i < 12; i++) {
twopows[i] = r;
r *= 2;
}
//cerr << twopows;
for(ll i = 1; i <= n; i++) {
for(ll j = 0; j < v[i].size(); j++) {
out[i] += twopows[j] * v[i][j];
}
}
return out;
}
int main() {
setvbuf(stdout, NULL, _IONBF, 0);
setvbuf(stderr, NULL, _IONBF, 0);
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
vector<ll> v = solve(n);
cout << "! ";
for(ll i = 1; i <= n; i++) {
cout << v[i];
if(i < n) {
cout << " ";
}
}
cout.flush();
exit(0);
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Time limit exceeded | 1ms | 316 KiB | ||||
| subtask2 | 0/5 | ||||||
| 2 | Time limit exceeded | 1ms | 572 KiB | ||||
| subtask3 | 0/5 | ||||||
| 3 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask4 | 0/5 | ||||||
| 4 | Time limit exceeded | 1ms | 568 KiB | ||||
| subtask5 | 0/5 | ||||||
| 5 | Time limit exceeded | 1ms | 576 KiB | ||||
| subtask6 | 0/5 | ||||||
| 6 | Time limit exceeded | 1ms | 568 KiB | ||||
| subtask7 | 0/5 | ||||||
| 7 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask8 | 0/5 | ||||||
| 8 | Time limit exceeded | 1ms | 316 KiB | ||||
| subtask9 | 0/5 | ||||||
| 9 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask10 | 0/5 | ||||||
| 10 | Time limit exceeded | 1ms | 316 KiB | ||||
| subtask11 | 0/5 | ||||||
| 11 | Time limit exceeded | 1ms | 316 KiB | ||||
| subtask12 | 0/5 | ||||||
| 12 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask13 | 0/5 | ||||||
| 13 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask14 | 0/5 | ||||||
| 14 | Time limit exceeded | 1ms | 748 KiB | ||||
| subtask15 | 0/5 | ||||||
| 15 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask16 | 0/5 | ||||||
| 16 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask17 | 0/5 | ||||||
| 17 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask18 | 0/5 | ||||||
| 18 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask19 | 0/5 | ||||||
| 19 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask20 | 0/5 | ||||||
| 20 | Time limit exceeded | 1ms | 564 KiB | ||||
| subtask21 | 0/5 | ||||||
| 21 | Time limit exceeded | 1ms | 564 KiB | ||||