QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#569657 | #8267. Staring Contest | Keklord1945 | 0 | 3ms | 11712kb | C++23 | 4.1kb | 2024-09-17 03:31:51 | 2024-09-17 03:31:51 |
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());
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
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 1ms
memory: 3556kb
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: 3596kb
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: 0ms
memory: 3696kb
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: 5824kb
input:
50 17 37 28 17
output:
? 17 41 ? 41 37 ? 37 28 ? 28 17 3333 3333 ? 41 41
result:
wrong answer unknown command 3333
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 0ms
memory: 10220kb
input:
1000 610 406 270 270
output:
? 610 809 ? 809 406 ? 406 270 ? 270 610 4444 3333 3333 ? 809 809
result:
wrong answer unknown command 4444
Subtask #3:
score: 0
Wrong Answer
Test #88:
score: 0
Wrong Answer
time: 3ms
memory: 11712kb
input:
1500 776 904 708 708
output:
? 776 1382 ? 1382 904 ? 904 708 ? 708 776 3333 3333 3333 ? 904 904
result:
wrong answer unknown command 3333