QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#617079 | #6308. Magic | fryan | WA | 0ms | 3656kb | C++20 | 1009b | 2024-10-06 13:49:43 | 2024-10-06 13:49:47 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
mt19937 rng(1);
const int mxn = 5e3+5;
int n;
int l[mxn], r[mxn];
bitset<mxn> adj[mxn],used;
int mt[mxn];
bool kuhn(int v) {
used.reset(v);
auto nx = adj[v];
nx &= used;
for (int i=nx._Find_first(); i < nx.size(); i = nx._Find_next(i)) {
if (mt[i]==-1 || kuhn(mt[i])) {
mt[i] = v;
return 1;
}
nx &= used;
}
return 0;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin>>n;
for (int i=0; i<n; i++) {
cin>>l[i]>>r[i];
adj[i].reset();
}
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (l[i] < l[j] && r[i] > l[j] && r[i] < r[j])
adj[j].set(i);
}
}
memset(mt,-1,sizeof(mt));
for (int v=0; v<n; v++) {
used.set();
kuhn(v);
}
int cnt = 2*n;
for (int i=0; i<n; i++) {
if (mt[i] != -1) {
cout<<i<<" "<<mt[i]<<"\n";
cnt--;
}
}
cout<<cnt;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3656kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
2 3 9
result:
wrong answer 1st numbers differ - expected: '9', found: '2'