QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569674 | #8267. Staring Contest | Keklord1945 | 0 | 2ms | 10840kb | C++23 | 4.2kb | 2024-09-17 04:12:54 | 2024-09-17 04:12:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef natural_selection
#include "/dbg.h"
#else
#define endl "\n"
#define debug(...)
#endif
struct Random : std::mt19937
{
using std::mt19937::mt19937;
using std::mt19937::operator();
static int64_t gen_seed()
{
return std::chrono::steady_clock::now().time_since_epoch().count();
}
Random() : std::mt19937(gen_seed()) {}
template <class Int>
auto operator()(Int a, Int b)
-> std::enable_if_t<std::is_integral_v<Int>, Int>
{
return std::uniform_int_distribution<Int>(a, b)(*this);
}
template <class Int>
auto operator()(Int a) -> std::enable_if_t<std::is_integral_v<Int>, Int>
{
return std::uniform_int_distribution<Int>(0, a - 1)(*this);
}
template <class Real>
auto operator()(Real a, Real b)
-> std::enable_if_t<std::is_floating_point_v<Real>, Real>
{
return std::uniform_real_distribution<Real>(a, b)(*this);
}
};
const int N = 1505, B = 86401;
int val[N][N];
int32_t main()
{
Random rng;
int n;
cin >> n;
vector<int> a(n);
iota(a.begin(), a.end(), 0);
random_shuffle(a.begin(), a.end(), rng);
auto ask = [&](int u, int v) -> int
{
// assert(u != v);
if(val[u][v] == 0)
{
cout << "?" << " " << u + 1 << " " << v + 1 << endl;
cin >> val[u][v];
val[v][u] = val[u][v];
}
return val[u][v];
};
vector<int> ans(n, B);
while((int)a.size() >= 4)
{
// assert((int)a.size() >= 4); ok
vector<int> b(4);
for(int i = 0; i < 4; i ++)
b[i] = a.back(), a.pop_back();
random_shuffle(b.begin(), b.end(), rng);
vector<int> f(4, B);
for(int i = 0; i < 4; i ++)
f[i] = ask(b[i], b[(i + 1) % 4]);
int cnt = set<int>(f.begin(), f.end()).size();
if(cnt == 2)
{
for(int i = 0; i < 4; i ++)
if(f[i] == f[(i - 1 + 4) % 4])
ans[b[i]] = f[i];
int ins = 0;
for(int i = 0; i < 4; i ++)
if(ans[b[i]] == B)
++ ins, a.push_back(b[i]);
// assert(ins == 2);
}
else if(cnt == 3)
{
int mn = *min_element(f.begin(), f.end());
int mx = *max_element(f.begin(), f.end());
int now=-1;
for(int i = 0; i < 4; i ++)
{
if(f[i] == f[(i - 1 + 4) % 4])
ans[b[i]] = f[i], now=i;
else if(f[i] != mn and f[i] != mx)
{
if(f[(i - 1 + 4) % 4] == mn)
ans[b[i]] = f[i];
if(f[(i + 1) % 4] == mn)
ans[b[(i + 1) % 4]] = f[i];
}
vector<int>ins;
for(int i = 0; i < 4; i ++)
if(ans[b[i]] == B)
ins.push_back(i), a.push_back(b[i]);
//assert(ins == 2);
if(ins.size()!=2) cout << f[0] << 0 << f[1] << 0 << f[2] << 0 << f[3] << 0 << ins[0] << 0 << ins[1] << 0 << ins[2] << 0 << now<< endl;
}
}
}
if((int)a.size() == 3)
{
vector<int> b(3);
for(int i = 0; i < 3; i ++)
b[i] = a.back(), a.pop_back();
random_shuffle(b.begin(), b.end(), rng);
vector<int> f(3, B);
for(int i = 0; i < 3; i ++)
f[i] = ask(b[i], b[(i + 1) % 3]);
int m = *min_element(f.begin(), f.end());
for(int i = 0; i < 3; i ++)
{
if(f[i] != m)
{
if(a.empty())
ans[b[i]] = ans[b[(i + 1) % 3]] = f[i];
else
a.push_back(b[i]), a.push_back(b[(i + 1) % 3]);
ans[b[(i - 1 + 3) % 3]] = m;
}
}
}
else if((int)a.size() == 2)
ans[a[0]] = ans[a[1]] = ask(a[0], a[1]);
cout << "!" << " ";
for(auto x : ans)
cout << x << " ";
cout << endl;
}
/*
4 5 3 2 6 8
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 1ms
memory: 3540kb
input:
2 1
output:
? 1 2 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #2:
score: 9
Accepted
time: 0ms
memory: 3556kb
input:
2 1
output:
? 2 1 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #3:
score: 9
Accepted
time: 0ms
memory: 3648kb
input:
2 1
output:
? 1 2 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 3868kb
input:
50 37 37 42 42 20 3 3 47
output:
? 50 37 ? 37 47 ? 47 42 ? 42 50 ? 47 20 ? 20 3 ? 3 50 ? 50 47 2003030470002030-1 2003030470002030-1 ? 50 23
result:
wrong answer unknown command 2003030470002030-1
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 2ms
memory: 10840kb
input:
1000 86 372 372 86 617 489 489 617 624 624 343 343 935 646 646 882
output:
? 86 489 ? 489 372 ? 372 882 ? 882 86 ? 617 882 ? 882 489 ? 489 935 ? 935 617 ? 935 624 ? 624 882 ? 882 343 ? 343 935 ? 935 999 ? 999 646 ? 646 882 ? 882 935 9350646064608820001020-1 9350646064608820001020-1 93506460646088200010302 ? 999 999
result:
wrong answer unknown command 9350646064608820001020-1
Subtask #3:
score: 0
Runtime Error
Test #88:
score: 0
Runtime Error
input:
1500 1172 1172 943 943 1339 294 294 1339 1368 1364 406 406
output:
? 1339 1172 ? 1172 1400 ? 1400 943 ? 943 1339 ? 1339 1400 ? 1400 294 ? 294 1368 ? 1368 1339 ? 1368 1400 ? 1400 1364 ? 1364 406 ? 406 1368 136801364040604060001020-1 136801364040604060001030-1 136801364040604060001030-1 ? 406 1400