QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #583393 | #6414. Classical Maximization Problem | huaxiamengjin# | WA | 133ms | 11804kb | C++14 | 1.8kb | 2024-09-22 19:48:06 | 2024-09-22 19:48:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,tot;
int ct[200100],ct2[200100];
vector<int>g[200100];
int a[400200];
int x[200100],y[200100];
vector<int>s;
int used[200100];
void solve(){
cin>>n;tot=0;n*=2;
for (int i=1;i<=n;i++)
cin>>x[i]>>y[i],a[++tot]=x[i],a[++tot]=y[i],used[i]=0;
sort(a+1,a+tot+1);
tot=unique(a+1,a+tot+1)-a-1;
for (int i=1;i<=tot;i++)
g[i].clear(),ct[i]=0;
vector<pair<int,int> >ans;
int zong=0;
for (int i=1;i<=n;i++)
x[i]=lower_bound(a+1,a+tot+1,x[i])-a,
y[i]=lower_bound(a+1,a+tot+1,y[i])-a,
g[x[i]].push_back(i);
for (int i=1;i<=tot;i++)
if(g[i].size()%2==0){
for (int j=0;j<g[i].size();j+=2)
ans.push_back({g[i][j],g[i][j+1]}),zong++;
}else{
int fl=-1;
for (int j=0;j<g[i].size();j++)
if(ct[y[g[i][j]]]!=0){fl=j;break;}
if(fl!=-1){
for (int j=0;j<g[i].size();j+=2){
if(fl==j)ans.push_back({g[i][j+1],g[i][j+2]}),zong++;
if(fl==j+1)ans.push_back({g[i][j],g[i][j+2]}),zong++;
else ans.push_back({g[i][j],g[i][j+1]}),zong++;
if(fl==j||fl==j+1)j++;
}
int ii=ct[g[i][fl]],fll=fl;
for (int j=0;j<g[ii].size();j++)
if(y[g[ii][j]]==y[g[i][fl]]){fl=j;break;}
for (int j=0;j<g[ii].size();j+=2){
if(fl==j)ans.push_back({g[ii][j+1],g[ii][j+2]}),zong++;
if(fl==j+1)ans.push_back({g[ii][j],g[ii][j+2]}),zong++;
else ans.push_back({g[ii][j],g[ii][j+1]}),zong++;
if(fl==j||fl==j+1)j++;
}
for (auto j:g[ii])ct[y[j]]=0;
ans.push_back({g[i][fll],g[ii][fl]});zong++;
}else{
for (auto j:g[i])ct[y[j]]=i;
}
}
vector<int>t;
for (int i=1;i<=tot;i++){
if(ct[i]!=0){
for (auto j:g[i])
t.push_back(j),ct[y[j]]=0;
}
}
for (int i=0;i<t.size();i+=2)
ans.push_back({t[i],t[i+1]});
cout<<zong<<"\n";
for (auto i:ans)
cout<<i.first<<" "<<i.second<<"\n";
}
int main(){
int T;cin>>T;
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11724kb
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 1 2 3 4 2 1 2 3 4 0 1 2 3 4
result:
ok ok (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 133ms
memory: 11804kb
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 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 ...
result:
wrong answer Integer parameter [name=a[1]] equals to 0, violates the range [1, 4] (test case 1)