QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#166317 | #6414. Classical Maximization Problem | xuzhihaodedie | WA | 111ms | 11056kb | C++14 | 1.5kb | 2023-09-06 08:30:04 | 2023-09-06 08:30:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define x first
//#define y second
#define PII pair<int,int>
const int N=2e5+10;
const int mod=998244353;
vector<PII> g[N];
int vis[N];
int use[N];
vector<PII> ans;
void dfs(int x,int fa) {
vis[x]=1;
for(auto p:g[x]) {
int y=p.first;
if(!vis[y]) dfs(y,x);
}
int last=0;
int f=0;
for(auto p:g[x]) {
if(use[p.second]) continue;
int y=p.first;
if(y==fa) f=p.second;
else {
if(!last) last=p.second;
else {
ans.push_back({last,p.second});
use[last]=use[p.second]=1;
last=0;
}
}
}
if(last&&f) {
ans.push_back({last,f});
use[last]=use[f]=1;
}
}
void solve() {
int n;
cin>>n;
int cnt=0;
map<int,int> mp1,mp2;
ans.clear();
for(int i=1;i<=2*n;i++) g[i].clear(),use[i]=0;
for(int i=1;i<=2*n;i++) {
int x,y;
cin>>x>>y;
if(!mp1[x]) mp1[x]=++cnt;
if(!mp2[y]) mp2[y]=++cnt;
x=mp1[x],y=mp2[y];
g[x].push_back({y,i});
g[y].push_back({x,i});
//cout<<x<<" "<<y<<endl;
}
for(int i=1;i<=2*n;i++) vis[i]=0;
for(int i=1;i<=cnt;i++) {
if(!vis[i]) {
dfs(i,0);
}
}
cout<<ans.size()<<endl;
for(auto p:ans) cout<<p.first<<" "<<p.second<<endl;
vector<int> v;
int f=0;
for (int i=1;i<=2*n;i++)
if (use[i]==0){
printf("%d",i);
if (f) printf("\n");
else printf(" ");
f=1-f;
}
}
signed main() {
int T=1;
cin>>T;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(T--) {
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10568kb
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 2 1 2 3 4 0 1 2 3 4
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 111ms
memory: 11056kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 1 2 3 4 5 6 1 2 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22...
result:
wrong answer Integer parameter [name=a[1]] equals to 0, violates the range [1, 4] (test case 1)