QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#574106 | #6439. Cloud Retainer's Game | ji_114514 | WA | 216ms | 6024kb | C++20 | 2.1kb | 2024-09-18 20:48:16 | 2024-09-18 20:48:16 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
struct node {
int x, y, c;
} a[N];
int h, n, m;
bool cmp(node i, node j) {
return i.x < j.x;
}
map<int, int>ha, hb;
//ha x-y hb x+y
int get(int x, int y, bool tag) {
int res = 0;
int a = (x - y + 2 * h) % (2 * h), b = (x + y + 2 * h) % (2 * h);
if (tag) {
if (hb.count(a))res = max(res, hb[a]);
if (ha.count(a))res = max(res, ha[a]);
}
else {
if (ha.count(b))res = max(res, ha[b]);
if (hb.count(b))res = max(res, hb[b]);
}
return res;
}
void solve()
{
cin >> h >> n;
ha.clear(), hb.clear();
for (int i = 1; i <= n; i++)cin >> a[i].x >> a[i].y, a[i].c = 0;
cin >> m;
for (int i = 1; i <= m; i++)cin >> a[i + n].x >> a[i + n].y, a[i + n].c = 1;
sort(a + 1, a + 1 + n + m, cmp);
ha[0] = 1; int ans = 1;
for (int i = 1; i <= n + m; i++) {
int x = a[i].x, y = a[i].y;
int s = (x - y + 2 * h) % (2 * h), t = (x + y + 2 * h) % (2 * h);
if (a[i].c) {
int res = get(a[i].x, a[i].y, 0);
if (res)hb[t] = max(hb[t], res + 1), ans = max(ans, res + 1);
//cout << x << ' ' << y << ' ' << a[i].c << ' ' << res << endl;
res = get(a[i].x, a[i].y, 1);
if (res)ha[s] = max(ha[s], res + 1), ans = max(ans, res + 1);
//cout << x << ' ' << y << ' ' << a[i].c << ' ' << res << endl;
}
else {
int res = get(a[i].x, a[i].y, 0);
if (res)ha[s] = max(ha[s], res), hb[t] = max(hb[t], res), ans = max(ans, res);
///cout<<x<<' '<<y<<' '<<a[i].c<<' '<<res<<endl;
res = get(a[i].x, a[i].y, 1);
if (res)hb[t] = max(hb[t], res), ha[s] = max(ha[s], res), ans = max(ans, res);
//cout<<x<<' '<<y<<' '<<a[i].c<<' '<<res<<endl;
}
}
cout << ans - 1 << '\n';
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
2 4 3 1 1 2 2 6 2 4 3 1 3 3 5 1 7 3 3 1 4 2 3 1 1 6 2 9 1
output:
3 3
result:
ok 2 number(s): "3 3"
Test #2:
score: -100
Wrong Answer
time: 216ms
memory: 6024kb
input:
5503 10 19 2 4 2 8 8 3 8 4 8 7 2 7 2 6 1 5 3 2 6 4 2 1 4 5 2 5 7 1 4 7 5 7 2 2 8 6 8 1 12 5 1 4 8 5 2 6 1 3 6 1 1 1 7 7 2 5 6 6 8 1 2 3 5 10 5 9 5 10 7 6 6 5 7 1 3 9 6 8 8 8 6 4 2 9 5 4 4 2 10 9 2 3 2 1 7 1 4 3 14 4 6 6 1 2 1 7 6 2 3 4 4 5 3 6 5 1 4 3 4 3 2 6 2 8 6 8 2 6 6 5 2 5 1 3 1 2 3 7 4 5 5 3 ...
output:
2 1 2 1 3 2 0 2 4 6 1 2 0 0 1 2 1 1 0 1 0 0 2 1 1 3 2 3 3 2 1 2 0 1 5 1 1 1 0 1 3 1 2 3 3 3 2 1 0 3 1 2 2 0 4 1 1 0 1 2 2 2 1 1 1 1 2 3 2 2 2 1 1 3 1 3 0 0 3 4 5 1 1 1 1 1 0 2 0 0 3 0 2 1 1 1 0 3 2 1 3 4 3 2 2 4 2 4 2 1 2 1 0 1 3 0 3 0 2 1 0 2 5 1 2 2 1 0 1 3 0 2 3 1 4 2 2 0 2 3 2 0 0 3 1 1 1 1 3 2 ...
result:
wrong answer 4010th numbers differ - expected: '4', found: '3'