QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#574285 | #6439. Cloud Retainer's Game | ji_114514 | WA | 433ms | 6436kb | C++20 | 1.9kb | 2024-09-18 21:23:53 | 2024-09-18 21:23:55 |
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) % (2 * h), b = ((x + y) % (2 * h) + 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) % (2 * h), t = ((x + y) % (2 * h) + 2 * h) % (2 * h);
if (a[i].c) {
int res0 = get(a[i].x, a[i].y, 0), res1 = get(a[i].x, a[i].y, 1);
if (res0)ha[s] = max(ha[s], res0 + 1), ans = max(ans, res0 + 1);
//cout << x << ' ' << y << ' ' << a[i].c << ' ' << res << endl;
if (res1)hb[t] = max(hb[t], res1 + 1), ans = max(ans, res1 + 1);
//cout << x << ' ' << y << ' ' << a[i].c << ' ' << ans << endl;
}
else {
int res = max(get(a[i].x, a[i].y, 1), get(a[i].x, a[i].y, 0));
ha[s] = max(ha[s], res), hb[t] = max(hb[t], 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: 3672kb
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: 433ms
memory: 6436kb
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:
1 1 3 2 3 4 0 3 4 5 2 2 0 0 1 1 2 1 0 4 0 0 2 1 1 2 4 3 2 3 1 3 0 1 3 1 1 2 0 1 3 2 2 3 2 4 1 2 0 2 1 2 1 0 4 1 2 0 1 2 3 2 1 1 1 1 2 2 3 3 3 1 1 2 1 3 0 0 2 3 4 1 1 1 1 1 0 3 0 0 2 0 2 1 2 1 0 4 3 1 2 3 2 1 1 3 3 2 3 1 2 1 0 2 3 0 5 0 2 1 0 2 3 1 2 1 1 0 2 1 0 3 3 1 3 2 1 0 2 2 3 0 0 3 1 2 1 1 2 1 ...
result:
wrong answer 1st numbers differ - expected: '2', found: '1'