QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569655 | #8267. Staring Contest | Keklord1945 | 0 | 2ms | 9864kb | C++23 | 4.1kb | 2024-09-17 03:25:43 | 2024-09-17 03:25:43 |
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 = 1500, 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());
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)
{
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];
}
int ins = 0;
for(int i = 0; i < 4; i ++)
if(ans[b[i]] == B)
++ ins, a.push_back(b[i]);
//assert(ins == 2);
if(ins!=2) cout << ins << ins << ins << ins << 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: 3588kb
input:
2 1
output:
? 2 1 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #2:
score: 9
Accepted
time: 0ms
memory: 3544kb
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: 3676kb
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: 3864kb
input:
50 30 36 19 19
output:
? 30 36 ? 36 45 ? 45 19 ? 19 30 3333 3333 3333 ? 45 45
result:
wrong answer unknown command 3333
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 0ms
memory: 8244kb
input:
1000 400 538 27 27
output:
? 400 571 ? 571 538 ? 538 27 ? 27 400 3333 3333 3333 ? 538 538
result:
wrong answer unknown command 3333
Subtask #3:
score: 0
Wrong Answer
Test #88:
score: 0
Wrong Answer
time: 2ms
memory: 9864kb
input:
1500 810 1024 1024 810 354 1071 576 354
output:
? 810 1071 ? 1071 1024 ? 1024 1248 ? 1248 810 ? 354 1248 ? 1248 1071 ? 1071 576 ? 576 354 3333 3333 ? 576 576
result:
wrong answer unknown command 3333