QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#182568#6414. Classical Maximization ProblemjackwasWA 81ms8552kbC++143.2kb2023-09-18 08:42:192023-09-18 08:42:20

Judging History

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

  • [2023-09-18 08:42:20]
  • 评测
  • 测评结果:WA
  • 用时:81ms
  • 内存:8552kb
  • [2023-09-18 08:42:19]
  • 提交

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)