QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#182568 | #6414. Classical Maximization Problem | jackwas | WA | 81ms | 8552kb | C++14 | 3.2kb | 2023-09-18 08:42:19 | 2023-09-18 08:42:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define el << '\n'
#define spe << ' '
#define sp spe <<
#define umap unordered_map
#define uset unordered_set
#define prqu priority_queue
#define fornr(i, j, n) for (int i = j; i < n; i++)
#define forn(i, n) for (int i = 0; i < n; i++)
#define forn1(i, n) for (int i = 1; i <= n; i++)
#define fornrb(i, j, n) for (int i = n - 1; i >= j; i--)
#define fornb(i, n) for (int i = n - 1; i >= 0; i--)
#define forn1b(i, n) for (i = n; i > 0; i--)
#define fornn(i, n) for (int i = 1; i <= n; i++)
#define rety cout << "YES\n"; return 0;
#define retn cout << "NO\n"; return 0;
#define conty cout << "YES\n"; continue;
#define contn cout << "NO\n"; continue;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
const int IMX = 2e9 + 5;
const ll LMX = 4e18 + 10, MOD = 1e9 + 7, MOD2 = 998244353;
const int MAXN = 1e5 + 5;
int x[MAXN], y[MAXN], n;
vector<int> gx[MAXN], gy[MAXN], ans1, ans2;
bool visited[MAXN], used[MAXN];
void dfs(int p, int f = MAXN - 1) {
visited[p] = 1;
forn(i, gx[x[p]].size()) {
int nx = gx[x[p]][i];
if (nx == p || nx == f) continue;
if (!visited[nx]) dfs(nx, p);
if (!used[p] && !used[nx]) {
used[p] = 1;
used[nx] = 1;
ans1.pb(p);
ans2.pb(nx);
}
}
if (!used[p] && f < n && !used[f]) {
used[f] = 1;
used[p] = 1;
ans1.pb(f);
ans2.pb(p);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> n;
n *= 2;
set<int> xv, yv;
vector<int> sx, sy;
forn(i, n) {
cin >> x[i] >> y[i];
if (xv.insert(x[i]).second) sx.pb(x[i]);
if (yv.insert(y[i]).second) sy.pb(y[i]);
visited[i] = 0;
used[i] = 0;
gx[i].clear();
gy[i].clear();
ans1.clear();
ans2.clear();
}
forn(i, n) {
int l = 0, r = sx.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (sx[m] == x[i]) {
l = m;
r = m;
} else if (sx[m] < x[i]) l = m + 1;
else r = m - 1;
}
x[i] = l;
l = 0, r = sy.size() - 1;
while (l < r) {
int m = (l + r) / 2;
if (sy[m] == y[i]) {
l = m;
r = m;
} else if (sy[m] < y[i]) l = m + 1;
else r = m - 1;
}
y[i] = l;
gx[x[i]].pb(i);
gy[y[i]].pb(i);
}
forn(i, n) {
if (!visited[i]) dfs(i);
}
cout << ans1.size() el;
forn(i, ans1.size()) cout << ans1[i] + 1 sp ans2[i] + 1 el;
vector<int> ans3;
forn(i, n) if (!used[i]) ans3.pb(i + 1);
forn(i, ans3.size()) {
cout << ans3[i] sp ans3[i + 1] el;
i++;
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 8504kb
input:
3 2 0 0 0 1 1 0 1 1 2 0 0 0 1 0 2 0 3 2 0 0 1 1 2 2 3 3
output:
2 1 2 3 4 2 3 1 4 2 0 1 2 3 4
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 81ms
memory: 8552kb
input:
10000 2 -107276936 -310501829 419434212 585811870 -65754386 -491212232 381152038 897148193 3 -474045168 493506332 299114415 540203303 165808153 983551 -506936261 -694189769 766718170 -725540031 975267148 -593051087 1 -818952276 -762387923 584023914 -612401389 6 -77701228 -266484128 659434465 6322062...
output:
1 4 1 2 3 1 1 4 2 3 5 6 0 1 2 5 9 1 11 7 5 2 8 3 10 12 4 6 3 9 2 10 4 13 6 1 3 5 7 8 11 12 14 1 1 2 28 54 1 6 2 11 3 19 12 37 13 14 4 15 8 23 17 24 18 28 25 30 27 40 34 41 38 49 42 51 48 56 52 57 55 63 59 66 60 10 5 20 9 29 21 31 22 43 32 44 39 65 47 53 7 46 26 16 33 35 36 45 50 58 61 62 64 1 4 1 2 ...
result:
wrong answer wrong number of friendly pairs: printed 1, but it is actually 0 (test case 1)