QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317859#6414. Classical Maximization ProblemMonaco114514WA 2ms12408kbC++143.9kb2024-01-29 20:44:342024-01-29 20:44:34

Judging History

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

  • [2024-01-29 20:44:34]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12408kb
  • [2024-01-29 20:44:34]
  • 提交

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));
    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: 0
Wrong Answer
time: 2ms
memory: 12408kb

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
0
4 1
2 3
0
2 3
4 1

result:

wrong answer wrong number of friendly pairs: printed 0, but it is actually 2 (test case 2)