QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569671 | #8267. Staring Contest | Keklord1945 | 0 | 3ms | 10944kb | C++23 | 4.1kb | 2024-09-17 04:03:40 | 2024-09-17 04:03:41 |
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];
else if(f[i] != mn and f[i] != mx)
{
ans[b[i]] = 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: 3672kb
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: 1ms
memory: 3672kb
input:
2 1
output:
? 1 2 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #3:
score: 9
Accepted
time: 1ms
memory: 3632kb
input:
2 1
output:
? 2 1 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 4060kb
input:
50 10 10 18 25
output:
? 32 10 ? 10 18 ? 18 25 ? 25 32 100100180250001020-1 100100180250002030-1 ? 25 25
result:
wrong answer unknown command 100100180250001020-1
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 2ms
memory: 9456kb
input:
1000 269 334 477 269
output:
? 269 334 ? 334 477 ? 477 783 ? 783 269 2690334047702690102030-1 ? 477 477
result:
wrong answer unknown command 2690334047702690102030-1
Subtask #3:
score: 0
Wrong Answer
Test #88:
score: 0
Wrong Answer
time: 3ms
memory: 10944kb
input:
1500 832 392 392 903
output:
? 903 832 ? 832 392 ? 392 998 ? 998 903 8320392039209030102030-1 8320392039209030102030-1 ? 832 832
result:
wrong answer unknown command 8320392039209030102030-1