QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569673 | #8267. Staring Contest | Keklord1945 | 0 | 1ms | 10700kb | C++23 | 4.2kb | 2024-09-17 04:08:04 | 2024-09-17 04:08:04 |
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)
{
if(f[(i - 1 + 4) % 4] == mn)
ans[b[i]] = f[i], now=i;
if(f[(i + 1) % 4] == mn)
ans[b[(i + 1) % 4]] = f[i],now=i+1;
}
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: 3600kb
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: 3740kb
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: 3664kb
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: 0ms
memory: 3856kb
input:
50 19 35 35 19 27 27 1 1 30 29 29 36
output:
? 19 36 ? 36 35 ? 35 42 ? 42 19 ? 36 27 ? 27 42 ? 42 1 ? 1 36 ? 36 30 ? 30 29 ? 29 42 ? 42 36 3002902903600020301 3002902903600020301 ? 42 42
result:
wrong answer unknown command 3002902903600020301
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 0ms
memory: 8252kb
input:
1000 10 10 513 580
output:
? 580 10 ? 10 513 ? 513 682 ? 682 580 10010051305800001020-1 10010051305800002030-1 ? 580 580
result:
wrong answer unknown command 10010051305800001020-1
Subtask #3:
score: 0
Wrong Answer
Test #88:
score: 0
Wrong Answer
time: 0ms
memory: 10700kb
input:
1500 943 10 10 118
output:
? 980 943 ? 943 10 ? 10 118 ? 118 980 94301001001180001020-1 94301001001180001020-1 94301001001180001030-1 ? 118 943
result:
wrong answer unknown command 94301001001180001020-1