QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54245 | #4575. Interactive Treasure Hunt | not_so_organic# | WA | 20ms | 3720kb | C++23 | 2.8kb | 2022-10-07 17:07:52 | 2022-10-07 17:07:54 |
Judging History
answer
#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define int long long
#define inf 1e18
using namespace std;
const int maxn = 1000005; // REMEMBER TO CHANGE UPPER BOUND
int mod = 1000000007, mod2 = 998244353, n, fac[maxn + 5], invfac[maxn + 5], arr[maxn + 5];
void mod998() {swap(mod, mod2);}
bool isprime(int k) {
for(int i = 2; i * i <= k; i++) if(k % i == 0) return false;
return true;
}
int bm(int a, int b) {
if(b == 0) return 1;
int t = bm(a, b / 2);
return (b % 2 == 1 ? t * t % mod * a % mod : t * t % mod);
}
int inv(int a) {return bm(a, mod - 2);}
int ncr(int n, int r) {
return (r > n ? 0LL : fac[n] * invfac[r] % mod * invfac[n - r] % mod);
}
void pre_fac(int n) {
fac[0] = 1; for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
}
void pre_invfac(int n) {
for(int i = 0; i <= n; i++) invfac[i] = inv(fac[i]);
}
int ask(int x, int y) {
cout << "SCAN " << x << ' ' << y << endl;
int a;
cin >> a;
return a;
}
int dist(int x1, int y1, int x2, int y2, int xx, int yy) {
return abs(x1 - xx) + abs(y1 - yy) + abs(x2 - xx) + abs(y2 - yy);
}
void solve(int TC) {
// cin >> n;
// for(int i = 1; i <= n; i++) cin >> arr[i]; // 1 BASED!!
int n, m;
cin >> n >> m;
int tl = ask(1, 1);
int tr = ask(1, m);
int avd = (tl + tr - (m - 1) * 2) / 2;
int mm = (tl - avd) / 2;
avd /= 2;
avd++; mm++;
int tm = ask(avd, mm);
int mmm = min(m, mm + tm / 2);
int tmm = ask(avd, mmm);
set<pair<pair<int, int>, pair<int, int>>> poss;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
for(int ii = 1; ii <= n; ii++) {
for(int jj = 1; jj <= m; jj++) {
if(ii == i && jj == j) continue;
if(tl != dist(i, j, ii, jj, 1, 1)) continue;
if(tr != dist(i, j, ii, jj, 1, m)) continue;
if(tm != dist(i, j, ii, jj, avd, mm)) continue;
if(tmm != dist(i, j, ii, jj, avd, mmm)) continue;
poss.insert(mp(mp(ii, jj), mp(i, j)));
}
}
}
}
// assert(poss.size() <= 4);
int lef = 2;
for(auto x: poss) {
cout << "DIG " << x.fi.fi << ' ' << x.fi.se << endl;
int a;
cin >> a;
if(a == 0) continue;
lef -= a;
cout << "DIG " << x.se.fi << ' ' << x.se.se << endl;
cin >> a;
if(a == 0) continue;
lef -= a;
if(lef == 0) return;
}
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 1;
cin >> t; // REMOVE THIS LINE IF ONLY 1 CASE
for(int i = 1; i <= t; i++) solve(i);
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
input:
1 2 3 3 1 1 1 1 1
output:
SCAN 1 1 SCAN 1 3 SCAN 1 2 SCAN 1 2 DIG 1 2 DIG 1 3
result:
ok (1 test case)
Test #2:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
72 3 3 1 5 1 1 1 1 3 3 4 4 4 4 0 1 1 3 3 5 5 3 3 0 1 1 3 2 2 4 2 4 1 1 3 3 5 1 1 1 1 1 3 2 3 3 3 3 1 1 3 3 4 4 2 4 1 1 2 3 3 3 3 3 1 1 3 3 3 5 1 1 1 1 3 3 1 3 1 1 1 1 3 3 3 3 3 3 0 1 1 2 3 3 3 3 3 0 1 1 3 2 1 1 1 1 1 1 3 2 4 4 2 2 1 1 2 3 3 3 1 1 1 1 3 3 4 2 2 2 0 1 1 2 3 3 1 1 1 1 1 3 3 2 4 2 2 0 1...
output:
SCAN 1 1 SCAN 1 3 SCAN 1 1 SCAN 1 1 DIG 1 1 DIG 2 1 SCAN 1 1 SCAN 1 3 SCAN 2 2 SCAN 2 3 DIG 1 1 DIG 1 3 DIG 3 1 SCAN 1 1 SCAN 1 3 SCAN 2 2 SCAN 2 3 DIG 2 1 DIG 2 3 DIG 3 1 SCAN 1 1 SCAN 1 2 SCAN 2 1 SCAN 2 2 DIG 1 1 DIG 3 1 SCAN 1 1 SCAN 1 3 SCAN 1 3 SCAN 1 3 DIG 1 3 DIG 2 3 SCAN 1 1 SCAN 1 2 SCAN 2...
result:
ok (72 test cases)
Test #3:
score: 0
Accepted
time: 10ms
memory: 3648kb
input:
100 2 16 15 17 15 15 0 1 1 2 4 6 2 2 2 0 1 1 2 15 18 12 2 2 1 1 2 5 3 9 1 1 1 1 2 13 14 14 12 12 1 1 2 15 16 14 14 14 0 1 1 2 5 7 3 1 1 1 1 2 6 6 6 6 6 0 1 1 2 4 2 4 2 2 1 1 2 16 20 12 12 12 1 1 2 13 17 11 9 9 1 1 2 8 8 8 8 8 0 1 1 2 12 10 12 8 8 1 1 2 12 15 11 9 9 1 1 2 12 1 21 1 1 1 1 2 15 19 9 1 ...
output:
SCAN 1 1 SCAN 1 16 SCAN 1 8 SCAN 1 15 DIG 1 1 DIG 1 15 DIG 2 1 SCAN 1 1 SCAN 1 4 SCAN 1 3 SCAN 1 4 DIG 1 3 DIG 1 4 DIG 2 3 SCAN 1 1 SCAN 1 15 SCAN 1 9 SCAN 1 10 DIG 1 9 DIG 2 10 SCAN 1 1 SCAN 1 5 SCAN 2 1 SCAN 2 1 DIG 2 1 DIG 2 2 SCAN 1 1 SCAN 1 13 SCAN 2 7 SCAN 2 13 DIG 2 1 DIG 2 13 SCAN 1 1 SCAN 1...
result:
ok (100 test cases)
Test #4:
score: 0
Accepted
time: 6ms
memory: 3624kb
input:
100 7 2 6 4 2 2 1 1 10 2 17 15 1 1 1 1 12 2 9 11 7 9 1 1 6 2 11 11 1 1 1 1 14 2 16 14 10 10 1 1 7 2 7 7 7 7 1 1 16 2 21 19 7 7 1 1 13 2 8 8 4 4 1 1 15 2 8 10 4 6 1 1 9 2 6 6 6 6 0 1 1 11 2 15 13 1 1 1 1 13 2 13 11 5 5 1 1 15 2 18 18 6 6 1 1 5 2 5 7 1 1 1 1 8 2 7 7 3 3 0 1 1 11 2 8 6 4 4 1 1 14 2 22 ...
output:
SCAN 1 1 SCAN 1 2 SCAN 3 2 SCAN 3 2 DIG 2 2 DIG 4 2 SCAN 1 1 SCAN 1 2 SCAN 8 2 SCAN 8 2 DIG 8 2 DIG 9 2 SCAN 1 1 SCAN 1 2 SCAN 5 1 SCAN 5 2 DIG 2 1 DIG 9 1 SCAN 1 1 SCAN 1 2 SCAN 6 1 SCAN 6 1 DIG 6 1 DIG 6 2 SCAN 1 1 SCAN 1 2 SCAN 8 2 SCAN 8 2 DIG 3 2 DIG 13 2 SCAN 1 1 SCAN 1 2 SCAN 4 1 SCAN 4 2 DIG...
result:
ok (100 test cases)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
100 3 10 11 15 5 5 1 1 3 12 22 4 4 4 0 1 1 3 13 20 12 4 4 1 1 3 4 6 6 4 4 1 1 3 10 9 13 5 5 0 1 1 3 15 20 10 6 6 1 1 3 13 16 10 4 4 1 1 3 16 13 23 1 1 1 1 3 12 7 15 1 1 1 1 3 8 7 13 1 1 1 1 3 13 17 13 11 11 1 1 3 9 10 10 2 2 1 1 3 9 6 14 4 6 0 1 1 3 11 11 13 11 11 0 1 1 3 4 2 8 2 4 1 1 3 7 13 7 3 3 ...
output:
SCAN 1 1 SCAN 1 10 SCAN 3 4 SCAN 3 6 DIG 3 2 DIG 3 7 SCAN 1 1 SCAN 1 12 SCAN 2 11 SCAN 2 12 DIG 1 10 DIG 1 12 DIG 3 10 SCAN 1 1 SCAN 1 13 SCAN 3 9 SCAN 3 11 DIG 3 7 DIG 3 11 SCAN 1 1 SCAN 1 4 SCAN 2 2 SCAN 2 4 DIG 2 1 DIG 3 4 SCAN 1 1 SCAN 1 10 SCAN 2 4 SCAN 2 6 DIG 1 3 DIG 1 6 DIG 3 3 SCAN 1 1 SCAN...
result:
ok (100 test cases)
Test #6:
score: 0
Accepted
time: 20ms
memory: 3564kb
input:
100 7 3 10 14 2 4 1 1 5 3 6 4 4 4 0 1 1 5 3 6 10 2 4 1 1 6 3 9 9 3 3 1 1 6 3 7 3 3 3 1 1 10 3 11 11 7 7 1 1 15 3 31 29 1 1 1 1 16 3 12 10 10 10 0 1 1 11 3 9 9 7 7 1 1 15 3 27 23 3 3 1 1 6 3 6 8 6 8 1 1 12 3 18 14 8 8 1 1 4 3 3 7 1 1 1 1 14 3 18 16 10 10 0 1 1 8 3 11 11 1 1 1 1 16 3 11 13 3 3 0 1 1 1...
output:
SCAN 1 1 SCAN 1 3 SCAN 6 1 SCAN 6 2 DIG 5 1 DIG 7 1 SCAN 1 1 SCAN 1 3 SCAN 2 2 SCAN 2 3 DIG 1 2 DIG 1 3 DIG 4 2 SCAN 1 1 SCAN 1 3 SCAN 4 1 SCAN 4 2 DIG 3 1 DIG 5 1 SCAN 1 1 SCAN 1 3 SCAN 4 2 SCAN 4 3 DIG 4 1 DIG 5 3 SCAN 1 1 SCAN 1 3 SCAN 2 3 SCAN 2 3 DIG 1 3 DIG 4 3 SCAN 1 1 SCAN 1 3 SCAN 5 2 SCAN ...
result:
ok (100 test cases)
Test #7:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
100 10 6 15 15 1 1 1 1 4 8 1 13 1 1 1 1 2 2 1 1 1 1 1 1 15 6 10 6 6 6 0 1 1 7 4 3 7 3 3 1 1 4 4 7 9 3 3 0 1 1 12 10 26 26 6 8 1 1 11 3 8 10 8 10 1 1 6 11 16 14 4 4 0 1 1 3 11 17 9 7 7 0 1 1 7 8 12 14 8 12 1 1 16 12 16 20 10 14 0 1 1 15 11 19 17 9 15 1 1 16 9 16 20 2 2 1 1 4 16 6 28 6 8 1 1 8 9 19 19...
output:
SCAN 1 1 SCAN 1 6 SCAN 6 3 SCAN 6 3 DIG 6 3 DIG 6 4 SCAN 1 1 SCAN 1 8 SCAN 1 1 SCAN 1 1 DIG 1 1 DIG 1 2 SCAN 1 1 SCAN 1 2 SCAN 1 1 SCAN 1 1 DIG 1 1 DIG 1 2 SCAN 1 1 SCAN 1 6 SCAN 2 4 SCAN 2 6 DIG 1 3 DIG 1 6 DIG 4 3 SCAN 1 1 SCAN 1 4 SCAN 2 1 SCAN 2 2 DIG 1 1 DIG 3 2 SCAN 1 1 SCAN 1 4 SCAN 3 2 SCAN ...
result:
ok (100 test cases)
Test #8:
score: -100
Wrong Answer
time: 13ms
memory: 3720kb
input:
100 11 15 20 12 10 12 0 1 1 15 11 10 30 10 20 1 1 16 13 15 17 7 7 1 1 11 16 30 26 16 20 1 1 10 12 21 31 3 3 1 1 15 11 21 33 13 23 0 1 1 13 13 31 31 11 13 0 1 1 15 14 19 33 5 9 1 1 14 10 34 36 4 4 1 1 14 15 23 19 7 7 0 1 1 11 13 25 21 15 19 0 1 1 14 15 35 35 15 19 1 1 15 15 27 27 15 23 0 1 1 11 11 21...
output:
SCAN 1 1 SCAN 1 15 SCAN 2 10 SCAN 2 15 DIG 1 6 DIG 1 14 DIG 3 6 SCAN 1 1 SCAN 1 11 SCAN 6 1 SCAN 6 6 DIG 1 1 DIG 11 1 SCAN 1 1 SCAN 1 13 SCAN 3 6 SCAN 3 9 DIG 2 4 DIG 4 9 SCAN 1 1 SCAN 1 16 SCAN 7 9 SCAN 7 16 DIG 4 5 DIG 11 14 SCAN 1 1 SCAN 1 12 SCAN 8 4 SCAN 8 5 DIG 8 3 DIG 9 5 SCAN 1 1 SCAN 1 11 S...
result:
wrong answer Asked more than 7 queries (test case 19)