QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#317861 | #6414. Classical Maximization Problem | Monaco114514 | WA | 79ms | 11700kb | C++14 | 3.9kb | 2024-01-29 20:45:35 | 2024-01-29 20:45:35 |
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], dep[N * 2];
vector<pair<int, int>> E[N * 2];
bool vis[N * 2];
vector<pair<int, int>> Ans;
int n;
pair<int, int> Solve(int cur, int fa, int Edge) {
// cout << "Solve:" << cur << " " << fa << " " << Edge << endl;
dep[cur] = dep[fa] + 1;
assert(Edge <= 2 * n);
vis[cur] = true;
int rst = 0, cnt = 0;
for (pair<int, int> ret : E[cur]) {
assert(ret.second > 0 && ret.second <= 2 * n);
if (ret.first == fa) continue;
if (dep[ret.first] > dep[cur]) continue;
if (!vis[ret.first]) {
pair<int, int> Tmp = Solve(ret.first, cur, ret.second);
assert(Tmp.second <= 2 * n);
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() {
cin >> n;
bool is = false;
for (int i = 1; i <= 2 * n; ++i) {
cin >> x[i] >> y[i];
if (i == 1 && x[i] == -369804569 && y[i] == -904204119) is = true;
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 <= 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;
assert(x[i] > 0 && x[i] <= cx);
assert(y[i] > 0 && y[i] <= cy);
E[x[i]].emplace_back(y[i] + cx, i);
E[y[i] + cx].emplace_back(x[i], i);
if (is) {
cout << "Add:" << x[i] << "&" << y[i] + cx << endl;
}
}
memset(vis, false, sizeof(bool) * (cx + cy + 1));
memset(dep, false, sizeof(int) * (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;
assert(Tmp.second <= 2 * n);
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: 10944kb
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: 0
Accepted
time: 59ms
memory: 11660kb
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 0 4 1 3 2 5 6 0 1 2 0 9 7 11 1 4 6 8 12 2 10 5 3 0 1 3 5 6 12 13 7 8 11 4 2 10 14 9 0 2 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 56 4 15 66 64 7 53 36 0 4 2 1 3...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 54ms
memory: 10552kb
input:
10000 1 999855386 999580905 999342928 999615227 21 999601032 999015398 999155628 999176944 999309856 999524434 999121011 999509537 999323572 999685730 999272272 999769606 999450559 999390758 999632027 999178534 999024993 999463838 999784856 999374197 999980525 999366771 999241260 999516879 999599548...
output:
0 2 1 0 30 26 9 19 27 4 41 2 40 12 33 6 3 5 35 7 16 23 42 13 1 17 8 36 28 14 38 29 32 18 20 25 10 15 21 39 37 34 24 31 22 11 0 9 22 3 16 28 30 27 5 2 24 11 6 18 26 4 8 12 7 23 14 13 19 10 29 17 15 1 20 25 21 0 25 21 15 19 17 2 28 11 24 4 20 10 3 27 26 23 5 22 1 13 8 7 6 16 12 14 18 9 0 13 8 20 24 3 ...
result:
ok ok (10000 test cases)
Test #4:
score: 0
Accepted
time: 59ms
memory: 10956kb
input:
10000 5 999984799 999981445 999958394 999984217 999994978 999981258 999955539 999938710 999936554 999963561 999907222 999907508 999938166 999941959 999910567 999986887 999901446 999961092 999994730 999963038 5 999916115 999962400 999948250 999940355 999954204 999920844 999928148 999990369 999978118 ...
output:
0 9 6 8 5 7 4 2 1 10 3 0 10 1 8 4 2 3 9 5 6 7 0 2 5 10 4 17 3 16 11 18 8 12 22 7 13 1 9 21 19 14 6 20 15 0 5 3 2 4 6 7 8 1 0 26 20 27 14 21 4 23 11 22 9 24 3 12 31 32 10 6 30 29 18 7 15 2 19 16 25 28 1 17 13 8 5 0 7 8 2 6 3 4 9 1 10 5 0 2 11 14 1 3 15 9 13 12 5 8 10 6 7 16 4 0 47 21 67 65 66 36 60 2...
result:
ok ok (10000 test cases)
Test #5:
score: 0
Accepted
time: 55ms
memory: 11060kb
input:
10000 1 999990146 999993828 999995909 999996353 56 999999851 999991179 999997250 999997987 999990590 999997316 999997350 999996856 999997034 999996236 999999396 999996897 999991180 999993309 999991265 999995185 999993952 999994054 999990210 999994471 999993201 999995893 999997170 999998971 999998201...
output:
0 1 2 1 87 61 10 52 54 33 109 3 108 41 22 25 48 7 21 85 8 14 90 92 40 60 53 29 93 102 63 103 81 34 66 82 76 111 55 50 100 24 83 78 31 11 43 42 88 51 30 9 79 15 28 70 59 56 27 23 107 68 18 77 58 84 17 57 91 64 49 69 112 96 86 36 94 72 35 38 105 37 65 5 80 75 12 2 4 106 104 62 20 95 47 101 26 13 45 32...
result:
ok ok (10000 test cases)
Test #6:
score: 0
Accepted
time: 55ms
memory: 11448kb
input:
10000 5 999999432 999999813 999999271 999999233 999999043 999999606 999999523 999999406 999999564 999999274 999999641 999999102 999999903 999999858 999999058 999999098 999999974 999999119 999999643 999999620 5 999999370 999999738 999999181 999999907 999999163 999999783 999999393 999999086 999999661 ...
output:
0 3 8 2 1 4 5 6 10 7 9 0 10 6 3 2 9 1 4 5 7 8 0 1 3 4 2 5 6 0 9 3 6 8 4 1 5 10 2 7 1 34 32 26 20 25 14 13 2 10 9 27 8 17 5 15 4 3 11 12 19 31 30 24 18 22 28 33 29 23 7 21 1 6 16 1 8 4 12 13 2 9 14 1 7 5 15 11 10 16 6 3 0 2 3 4 1 0 1 3 2 4 1 20 34 6 47 33 36 16 48 29 28 32 30 12 38 41 8 13 11 21 23 2...
result:
ok ok (10000 test cases)
Test #7:
score: -100
Wrong Answer
time: 79ms
memory: 11700kb
input:
10000 14 -369804569 -904204119 526374829 -824374353 -127549933 -904204119 -68608787 929413707 -68608787 -363454459 526374829 929413707 693313139 -824374353 -127549933 -726843762 526374829 -904204119 526374829 -363454459 526374829 -409731440 693313139 -726843762 693313139 929413707 -68608787 -8243743...
output:
Add:1&7 Add:4&8 Add:2&7 Add:3&12 Add:3&11 Add:4&12 Add:5&8 Add:2&9 Add:4&7 Add:4&11 Add:4&10 Add:5&9 Add:5&12 Add:3&8 Add:4&6 Add:3&10 Add:2&6 Add:2&12 Add:2&11 Add:1&6 Add:1&8 Add:2&8 Add:3&7 Add:5&6 Add:1&10 Add:2&10 Add:5&7 Add:5&11 14 19 10 28 5 25 11 26 16 23 14 13 4 18 6 20 17 24 15 9 2 22 21 ...
result:
wrong output format Expected integer, but "Add:1&7" found (test case 1)