QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54234 | #4575. Interactive Treasure Hunt | not_so_organic# | RE | 19ms | 3680kb | C++23 | 2.4kb | 2022-10-07 16:49:10 | 2022-10-07 16:49:13 |
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);
set<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(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;
poss.insert(mp(i, j));
poss.insert(mp(ii, jj));
}
}
}
}
assert(poss.size() <= 4);
int lef = 2;
for(auto x: poss) {
cout << "DIG " << x.fi << ' ' << x.se << endl;
int a;
cin >> a;
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);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3520kb
input:
1 2 3 3 1 1 1 1
output:
SCAN 1 1 SCAN 1 3 SCAN 1 2 DIG 1 2 DIG 1 3
result:
ok (1 test case)
Test #2:
score: 0
Accepted
time: 14ms
memory: 3680kb
input:
72 3 3 1 5 1 1 1 3 3 4 4 4 0 1 1 3 3 5 5 3 0 1 1 3 2 2 4 2 1 1 3 3 5 1 1 1 1 3 2 3 3 3 1 0 0 1 3 3 4 4 2 1 0 0 1 2 3 3 3 3 1 0 0 1 3 3 3 5 1 1 1 3 3 1 3 1 1 1 3 3 3 3 3 0 1 1 2 3 3 3 3 0 1 1 3 2 1 1 1 1 1 3 2 4 4 2 1 0 0 1 2 3 3 3 1 1 1 3 3 4 2 2 0 1 1 2 3 3 1 1 1 1 3 3 2 4 2 0 1 1 3 3 6 4 2 0 1 1 3...
output:
SCAN 1 1 SCAN 1 3 SCAN 1 1 DIG 1 1 DIG 2 1 SCAN 1 1 SCAN 1 3 SCAN 2 2 DIG 1 1 DIG 1 3 DIG 3 1 SCAN 1 1 SCAN 1 3 SCAN 2 2 DIG 2 1 DIG 2 3 DIG 3 1 SCAN 1 1 SCAN 1 2 SCAN 2 1 DIG 1 1 DIG 3 1 SCAN 1 1 SCAN 1 3 SCAN 1 3 DIG 1 3 DIG 2 3 SCAN 1 1 SCAN 1 2 SCAN 2 1 DIG 1 1 DIG 1 2 DIG 3 1 DIG 3 2 SCAN 1 1 S...
result:
ok (72 test cases)
Test #3:
score: 0
Accepted
time: 19ms
memory: 3624kb
input:
100 2 16 15 17 15 0 1 1 2 4 6 2 2 0 1 1 2 15 18 12 2 1 0 0 1 2 5 3 9 1 1 1 2 13 14 14 12 1 1 2 15 16 14 14 0 1 1 2 5 7 3 1 1 1 2 6 6 6 6 0 1 1 2 4 2 4 2 1 1 2 16 20 12 12 1 0 0 1 2 13 17 11 9 1 1 2 8 8 8 8 0 1 1 2 12 10 12 8 1 1 2 12 15 11 9 1 1 2 12 1 21 1 1 1 2 15 19 9 1 1 1 2 5 7 5 3 1 1 2 12 9 1...
output:
SCAN 1 1 SCAN 1 16 SCAN 1 8 DIG 1 1 DIG 1 15 DIG 2 1 SCAN 1 1 SCAN 1 4 SCAN 1 3 DIG 1 3 DIG 1 4 DIG 2 3 SCAN 1 1 SCAN 1 15 SCAN 1 9 DIG 1 9 DIG 1 10 DIG 2 9 DIG 2 10 SCAN 1 1 SCAN 1 5 SCAN 2 1 DIG 2 1 DIG 2 2 SCAN 1 1 SCAN 1 13 SCAN 2 7 DIG 2 1 DIG 2 13 SCAN 1 1 SCAN 1 15 SCAN 1 8 DIG 1 2 DIG 1 15 D...
result:
ok (100 test cases)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
100 7 2 6 4 2 1 1 10 2 17 15 1 1 1 12 2 9 11 7 1 1 6 2 11 11 1 1 1 14 2 16 14 10 1 1 7 2 7 7 7 1 0 0 1 16 2 21 19 7 1 1 13 2 8 8 4 1 0 0 1 15 2 8 10 4 1 1 9 2 6 6 6 0 1 1 11 2 15 13 1 1 1 13 2 13 11 5 1 1 15 2 18 18 6 1 0 0 1 5 2 5 7 1 1 1 8 2 7 7 3 0 1 1 11 2 8 6 4 1 1 14 2 22 22 4 0 1 1 16 2 29 29...
output:
SCAN 1 1 SCAN 1 2 SCAN 3 2 DIG 2 2 DIG 4 2 SCAN 1 1 SCAN 1 2 SCAN 8 2 DIG 8 2 DIG 9 2 SCAN 1 1 SCAN 1 2 SCAN 5 1 DIG 2 1 DIG 9 1 SCAN 1 1 SCAN 1 2 SCAN 6 1 DIG 6 1 DIG 6 2 SCAN 1 1 SCAN 1 2 SCAN 8 2 DIG 3 2 DIG 13 2 SCAN 1 1 SCAN 1 2 SCAN 4 1 DIG 1 1 DIG 1 2 DIG 7 1 DIG 7 2 SCAN 1 1 SCAN 1 2 SCAN 10...
result:
ok (100 test cases)
Test #5:
score: -100
Dangerous Syscalls
input:
100 3 10 11 15 5 1 1 3 12 22 4 4 0 1 1 3 13 20 12 4 1 1 3 4 6 6 4 1 0 0 1 3 10 9 13 5
output:
SCAN 1 1 SCAN 1 10 SCAN 3 4 DIG 3 2 DIG 3 7 SCAN 1 1 SCAN 1 12 SCAN 2 11 DIG 1 10 DIG 1 12 DIG 3 10 SCAN 1 1 SCAN 1 13 SCAN 3 9 DIG 3 7 DIG 3 11 SCAN 1 1 SCAN 1 4 SCAN 2 2 DIG 2 1 DIG 2 4 DIG 3 1 DIG 3 4 SCAN 1 1 SCAN 1 10 SCAN 2 4