QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#317859 | #6414. Classical Maximization Problem | Monaco114514 | WA | 2ms | 12408kb | C++14 | 3.9kb | 2024-01-29 20:44:34 | 2024-01-29 20:44:34 |
Judging History
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)