QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#569651 | #8267. Staring Contest | Keklord1945 | 0 | 1ms | 12100kb | C++23 | 4.0kb | 2024-09-17 03:19:49 | 2024-09-17 03:19:49 |
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 = 1500, B = 86400;
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((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: 3812kb
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: 1ms
memory: 3608kb
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: 3616kb
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: 0ms
memory: 3932kb
input:
50 13 13 44 38 38 13 8 11 8 44 46 11 2 2 18 4 4 4 37 18 15 23 15 23 14 28 28 14 6 40 3 3 3 40 41 5 5 41 34 34 21 21 35 19 19 35 42 42 10 10 43 43 20 20 26 26 33 45 45 48 33 26 27 29 12 12 12 29 9 29 17 9 17 39 16 16 36 17 36 1 25 16 1 49 25 7 22 47 31 31 24 49 24 50 30
output:
? 38 13 ? 13 44 ? 44 46 ? 46 38 ? 38 44 ? 46 13 ? 8 44 ? 46 11 ? 11 8 ? 44 44 ? 46 46 ? 44 11 ? 4 2 ? 2 37 ? 37 18 ? 18 4 ? 4 4 ? 37 4 ? 37 37 ? 18 18 ? 15 37 ? 37 23 ? 23 15 ? 23 23 ? 14 40 ? 40 28 ? 28 41 ? 41 14 ? 6 41 ? 41 40 ? 40 3 ? 3 6 ? 3 41 ? 40 40 ? 41 41 ? 42 5 ? 5 41 ? 41 42 ? 42 34 ? 34...
result:
wrong answer wrong answer b[36] <= a[36] not held.
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 0
Wrong Answer
time: 0ms
memory: 9212kb
input:
1000 378 378 656 656 57 57 297 790 856 790 297 57 243 681 806 229 229 856 229 150 349 427 150 907 427 674 349 347 75 510 777 797 567 696 696 780 98 70 51 51 98 51 51 272 70 98 410 272 37 37 272 470 470 829 829 831 852 365 365 365 996 357 852 160 160 160 160 952 583 327 327 583 450 450 421 421 585 45...
output:
? 790 378 ? 378 856 ? 856 656 ? 656 790 ? 856 57 ? 57 297 ? 297 790 ? 790 856 ? 856 856 ? 790 790 ? 856 297 ? 57 790 ? 856 243 ? 856 681 ? 806 856 ? 856 229 ? 229 806 ? 907 856 ? 229 907 ? 150 349 ? 349 427 ? 427 907 ? 907 150 ? 907 907 ? 427 427 ? 907 674 ? 907 349 ? 907 347 ? 907 75 ? 510 907 ? 90...
result:
wrong answer wrong answer b[455] <= a[455] not held.
Subtask #3:
score: 0
Wrong Answer
Test #88:
score: 0
Wrong Answer
time: 0ms
memory: 12100kb
input:
1500 385 385 68 68 757 228 228 757 437 776 387 387 387 776 1390 1390 1491 776 1491 1499 288 1241 1241 288 401 1190 912 401 1240 1190 912 1234 528 360 360 360 1376 1039 226 226 226 45 1373 1039 45 1373 221 221 417 918 1145 417 918 221 1058 874 448 448 874 920 42 42 920 203 932 970 203 1307 970 79 79 ...
output:
? 1390 385 ? 385 757 ? 757 68 ? 68 1390 ? 757 1390 ? 1390 228 ? 228 776 ? 776 757 ? 437 1390 ? 1390 776 ? 776 387 ? 387 437 ? 387 1390 ? 776 776 ? 1390 1390 ? 1390 1491 ? 1491 1499 ? 1499 776 ? 1491 1491 ? 1499 1499 ? 288 1499 ? 1499 1241 ? 1241 1491 ? 1491 288 ? 401 1190 ? 1190 1240 ? 1240 912 ? 91...
result:
wrong answer wrong answer b[558] <= a[558] not held.