QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317861#6414. Classical Maximization ProblemMonaco114514WA 79ms11700kbC++143.9kb2024-01-29 20:45:352024-01-29 20:45:35

Judging History

你现在查看的是最新测评结果

  • [2024-01-29 20:45:35]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:11700kb
  • [2024-01-29 20:45:35]
  • 提交

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)