QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#530196 | #8270. Mineral deposits | zwh2008 | 0 | 0ms | 0kb | C++14 | 3.2kb | 2024-08-24 15:22:29 | 2024-08-24 15:22:29 |
answer
#ifdef LOCAL
#include "stdafx.h"
#else
#include <bits/stdc++.h>
#define IL inline
#define LL long long
#define eb emplace_back
#define sz(v) ((int) (v).size())
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)
using namespace std;
using vi = vector<int>;
#endif
constexpr int inf = 1e8;
constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};
using pi = pair<int, int>;
using vp = vector<pi>;
#define fi first
#define se second
int k;
IL int dis (pi x, pi y) {
return abs(x.fi - y.fi) + abs(x.se - y.se);
}
vi query (vp probes) {
printf("?");
for (auto [x, y] : probes) {
printf(" %d %d", x, y);
}
printf("\n");
fflush(stdout);
vi d(sz(probes) * k);
L (i, 0, sz(d) - 1) {
scanf("%d", &d[i]);
}
return d;
}
constexpr int N = 1e6 + 9;
constexpr int M = 1e3 + 9;
pi ch[M], pts[M];
vi lis[M];
bool conf[M], used[N], vis[N];
vp solve (int b, int k, int w) {
vi st = query({{-b, b}, {-b, -b}});
set<pi> init;
for (int p : st) {
for (int q : st) {
if ((p + q) % 2) {
continue;
}
int x = (p + q - 2 * b) / 2 - b;
int y = p - (b + x) - b;
if (x < -b || x > b || y < -b || y > b) {
continue;
}
init.emplace(x, y);
}
}
vp dots(init.begin(), init.end());
int n = sz(dots);
vp ch, pts;
vector<vi> lis;
vector<bool> conf(n, false);
int lim = 4 * n * n;
vector<bool> used(lim + 1, false);
vector<bool> vis(lim + 1, false);
L (d, 0, lim) {
if (sz(ch) == n) {
break;
}
if (vis[d]) {
continue;
}
L (i, 0, n - 1) {
if (conf[i]) {
continue;
}
pi dot;
L (o, 0, 3) {
int x = dots[i].fi + dx[o] * d;
int y = dots[i].se + dy[o] * d;
if (x < -inf || x > inf || y < -inf || y > inf) {
continue;
}
bool fail = false;
L (j, 0, n - 1) {
if (i == j) {
continue;
}
int z = dis({x, y}, dots[j]);
if ((!conf[j] && z == d) || (z <= lim && used[z])) {
fail = true;
break;
}
}
if (fail) {
continue;
}
dot = {x, y};
goto found;
}
continue;
found:
vi cur;
L (j, 0, n - 1) {
int z = dis(dot, dots[j]);
if (z <= lim) {
if (z == d) {
cur.eb(j);
}
vis[z] = true;
}
}
ch.eb(i, d);
pts.eb(dot);
lis.eb(cur);
conf[i] = true;
used[d] = true;
break;
}
}
assert(sz(ch) == n);
vi ds = query(pts);
multiset<int> s(ds.begin(), ds.end());
conf.assign(n, false);
vp ns;
L (i, 0, n - 1) {
int cnt = 1;
for (int x : lis[i]) {
cnt ++;
}
if (s.count(ch[i].se) == cnt) {
int id = ch[i].fi;
ns.eb(dots[id]);
conf[id] = true;
}
}
assert(sz(ns) == k);
return ns;
}
int main () {
int b, w;
scanf("%d%d%d", &b, &k, &w);
vp ns = solve(b, k, w);
printf("!");
L (i, 0, k - 1) {
printf(" %d %d", ns[i].fi, ns[i].se);
}
printf("\n");
fflush(stdout);
}
// I love WHQ!
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
10 1 10000 20 30 2 7 9 10
output:
? -10 10 -10 -10 ? 0 0 5 -4 5 7 10 3
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Runtime Error
Test #116:
score: 0
Runtime Error
input:
100 20 3 64 75 90 91 93 99 113 132 136 152 158 162 166 174 177 179 188 189 190 197 197 200 202 205 214 225 226 227 229 229 242 254 261 268 270 277 283 314 327 335 40 45 47 48 49 52 55 56 57 60 61 67 68 68 69 70 72 72 73 75 75 77 77 78 79 80 81 84 84 86 86 88 88 89 89 90 90 91 92 92 94 95 96 98 98 98...
output:
? -100 100 -100 -100 ? -100 -36 -100 37 -98 -13 -98 14 -97 -16 -97 17 -94 -15 -94 16 -110 -44 -111 44 -123 -47 -265 -21 -289 21 -306 47 -316 -49 -322 -23 -341 0 -366 23 -393 49 -393 -51 -446 51 -456 -55 -498 55 -517 -31 -530 31 -529 -34 -540 34 -555 -62 -556 -51 -591 -36 -620 36 -711 51 -721 62 -736...
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%