QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#317844 | #6414. Classical Maximization Problem | Monaco114514 | WA | 116ms | 10552kb | C++14 | 3.4kb | 2024-01-29 20:21:13 | 2024-01-29 20:21:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using ull = unsigned long long;
bool Mbe;
#define TIME chrono::steady_clock::now().time_since_epoch().count()
#ifdef Monaco
int seed = 0;
#else
int seed = TIME;
#endif
mt19937 rnd(seed);
int rd(int l, int r) {
return rnd() % (r - l + 1) + l;
}
constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {
x += y, x >= mod && (x -= mod);
}
int add(int x, int y) {
return x += y, x >= mod && (x -= mod), x;
}
int ksm(int a, int b) {
int s = 1;
while (b) {
if (b & 1) s = 1ll * s * a % mod;
a = 1ll * a * a % mod, b >>= 1;
}
return s;
}
const int N = 1e5 + 8;
int lx[N * 2], ly[N * 2], x[N * 2], y[N * 2];
vector<pair<int, int>> E[N * 2];
bool vis[N * 2];
vector<pair<int, int>> Ans;
pair<int, int> Solve(int cur, int fa, int Edge) {
// cout << "Solve:" << cur << " " << fa << " " << Edge << endl;
vis[cur] = true;
int rst = 0, cnt = 0;
for (pair<int, int> ret : E[cur]) {
if (ret.first == fa) continue;
if (!vis[ret.first]) {
pair<int, int> Tmp = Solve(ret.first, cur, ret.second);
cnt += Tmp.first;
if (!Tmp.second) continue;
if (rst)
Ans.emplace_back(Tmp.second, rst), rst = 0, ++cnt;
else
rst = Tmp.second;
} else {
if (rst)
Ans.emplace_back(ret.second, rst), rst = 0, ++cnt;
else
rst = ret.second;
}
}
if (Edge) {
if (rst)
Ans.emplace_back(rst, Edge), ++cnt, rst = 0;
else
rst = Edge;
}
return make_pair(cnt, rst);
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= 2 * n; ++i) {
cin >> x[i] >> y[i];
lx[i] = x[i];
ly[i] = y[i];
}
sort(lx + 1, lx + 2 * n + 1);
int cx = unique(lx + 1, lx + 1 + 2 * n) - lx - 1;
sort(ly + 1, ly + 2 * n + 1);
int cy = unique(ly + 1, ly + 2 * n + 1) - ly - 1;
for (int i = 1; i <= max(cx, cy); ++i) E[i].clear();
for (int i = 1; i <= 2 * n; ++i) {
x[i] = lower_bound(lx + 1, lx + cx + 1, x[i]) - lx;
y[i] = lower_bound(ly + 1, ly + cy + 1, y[i]) - ly;
E[x[i]].emplace_back(y[i] + cx, i);
E[y[i] + cx].emplace_back(x[i], i);
}
memset(vis, false, sizeof(bool) * (cx + cy + 1));
int cnt = 0;
Ans.clear();
int rst = 0;
for (int i = 1; i <= cx + cy; ++i) {
if (!vis[i]) {
pair<int, int> Tmp = Solve(i, 0, 0);
cnt += Tmp.first;
if (!Tmp.second) continue;
if (rst)
Ans.emplace_back(rst, Tmp.second), rst = 0;
else
rst = Tmp.second;
}
}
cout << cnt << "\n";
for (pair<int, int> ret : Ans) cout << ret.first << " " << ret.second << "\n";
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef Monaco
FILE *IN = freopen("in.in", "r", stdin);
FILE *OUT = freopen("out.out", "w", stdout);
#endif
int T = 1;
cin >> T;
while (T--) solve();
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 9920kb
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 2 4 3 1 2 2 1 4 3 0 1 2 3 4
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 116ms
memory: 10552kb
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:
0 1 3 4 2 2 3 4 4 1 2 5 2 6 2 3 1 2 2 0 9 7 11 1 4 6 8 12 2 10 5 3 8 8 12 7 8 10 3 5 11 2 5 1 3 7 12 9 13 6 11 4 14 4 9 2 6 2 5 1 0 54 1 45 16 35 46 26 33 65 44 5 29 22 20 39 10 9 61 32 21 47 31 43 50 37 12 6 2 62 13 3 11 19 58 51 27 18 24 17 52 23 34 28 49 14 41 25 48 40 63 38 42 59 55 30 60 57 8 5...
result:
wrong answer point 4 used twice (test case 2)