QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#530196#8270. Mineral depositszwh20080 0ms0kbC++143.2kb2024-08-24 15:22:292024-08-24 15:22:29

Judging History

你现在查看的是最新测评结果

  • [2024-08-24 15:22:29]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [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%