QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317895#6414. Classical Maximization ProblemOrezTsimWA 0ms3908kbC++203.1kb2024-01-29 21:42:552024-01-29 21:42:56

Judging History

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

  • [2024-01-29 21:42:56]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3908kb
  • [2024-01-29 21:42:55]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

void solve() {
    int n,lena=0,lenb=0; cin>>n;
    vector<int>a((n<<1)+10,0),b((n<<1)+10,0);
    vector<int>la((n<<2)+10,0),lb((n<<2)+10,0);
    vector<bool>vis((n<<2)+10,false);
    for(int i=1;i<=(n<<1);++i)
        cin>>a[i]>>b[i],la[++lena]=a[i],lb[++lenb]=b[i];
    sort(la.begin()+1,la.begin()+1+lena);
    sort(lb.begin()+1,lb.begin()+1+lenb);
    lena=unique(la.begin()+1,la.begin()+1+lena)-la.begin()-1;
    lenb=unique(lb.begin()+1,lb.begin()+1+lenb)-lb.begin()-1;
    vector<vector<pair<int,int>>>g((n<<2)+10);
    for(int i=1;i<=(n<<1);++i) {
        a[i]=lower_bound(la.begin()+1,la.begin()+1+lena,a[i])-la.begin();
        b[i]=lower_bound(lb.begin()+1,lb.begin()+1+lenb,b[i])-lb.begin()+lena;
        g[a[i]].emplace_back(b[i],i),g[b[i]].emplace_back(a[i],i);
    }
    vector<pair<int,int>>res; int ret=0,edge=0;
    function<void(int,int)>dfs=[&](int x,int f,int fid=0) {
        vis[x]=true,edge+=g[x].size();
        vector<int>son; vector<pair<int,int>>bac;
        for(auto [to,id]: g[x]) {
            if(to==f) { fid=id; continue; }
            if(vis[to]) { bac.emplace_back(to,id); continue; }
            dfs(to,x),son.push_back(id);
        }
        if(!(son.size()&1)) {
            for(int i=1;i<son.size();i+=2)
                res.emplace_back(son[i-1],son[i]);
            for(int i=1;i<bac.size();i+=2) {
                res.emplace_back(bac[i-1].se,bac[i].se);
                int fir=bac[i-1].fi,sec=bac[i].fi;
                g[fir].erase(find(g[fir].begin(),g[fir].end(),make_pair(x,bac[i-1].se)));
                g[sec].erase(find(g[sec].begin(),g[sec].end(),make_pair(x,bac[i].se)));
            }
        } else {
            for(int i=1;i<son.size();i+=2)
                res.emplace_back(son[i-1],son[i]);
            if(!bac.empty()) {
                res.emplace_back(son.back(),bac[0].se);
                g[bac[0].fi].erase(find(g[bac[0].fi].begin(),g[bac[0].fi].end(),make_pair(x,bac[0].se)));
                for(int i=2;i<bac.size();i+=2) {
                    res.emplace_back(bac[i-1].se,bac[i].se);
                    int fir=bac[i-1].fi,sec=bac[i].fi;
                    g[fir].erase(find(g[fir].begin(),g[fir].end(),make_pair(x,bac[i-1].se)));
                    g[sec].erase(find(g[sec].begin(),g[sec].end(),make_pair(x,bac[i].se)));
                }
            } else if(fid) {
                res.emplace_back(son.back(),fid);
                g[f].erase(find(g[f].begin(),g[f].end(),make_pair(x,fid)));
            }
        }
    };
    for(int i=1;i<=lena+lenb;++i)
        if(!vis[i]) edge=0,dfs(i,edge),ret+=edge>>2;
    cout<<ret<<"\n"; vector<int>vec; vis.assign((n<<2)+10,false);
    for(auto [x,y]: res) cout<<x<<' '<<y<<"\n",vis[x]=vis[y]=true;
    for(int i=1;i<=(n<<1);++i) if(!vis[i]) vec.push_back(i);
    for(int i=1;i<vec.size();i+=2) cout<<vec[i-1]<<' '<<vec[i]<<"\n";
}

auto main() -> signed {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T; cin>>T;
    while(T--) solve();
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3908kb

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

result:

wrong answer point 3 used twice (test case 1)