QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#317844#6414. Classical Maximization ProblemMonaco114514WA 116ms10552kbC++143.4kb2024-01-29 20:21:132024-01-29 20:21:13

Judging History

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

  • [2024-01-29 20:21:13]
  • 评测
  • 测评结果:WA
  • 用时:116ms
  • 内存:10552kb
  • [2024-01-29 20:21:13]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)