QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#182567#6414. Classical Maximization ProblemjackwasWA 1ms8720kbC++143.0kb2023-09-18 08:40:192023-09-18 08:40:20

Judging History

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

  • [2023-09-18 08:40:20]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8720kb
  • [2023-09-18 08:40: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;
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 8720kb

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

result:

wrong output format Unexpected end of file - int32 expected (test case 3)