QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#604259 | #9412. Stop the Castle | ucup-team3474 | WA | 1ms | 3980kb | C++20 | 5.8kb | 2024-10-02 03:00:33 | 2024-10-02 03:00:33 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=314,M=N*N;
int h[N],ne[M],e[M],idx;
int match[N];
int n1,n2,m;
int n;
bool tf[M];
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool find(int x){
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(tf[j]==0){
tf[j]=1;
if(match[j]==0||find(match[j])){
match[j]=x;
return true;
}
}
}
return false;
}
PII d[N],dd[N];
vector<int> r[314],c[314];
vector<int> rid[314],cid[314];
PII mr[314],mc[314];
map<PII,int> mpd,mpz;
void check(int ii,int ri,int jj,int cj){
// for(int i=0)
// cout<<ii<<" "<<ri<<" "<<jj<<" "<<cj<<endl;
int val1=-1,val2=-1;
// for(auto x:r[ii]) cout<<x<<" ";
// cout<<endl;
// for(auto x:c[jj]) cout<<x<<" ";
// cout<<endl;
for(int i=1;i<r[ii].size();i++){
// cout<<r[ii][i-1]<<" "<<r[ii][i]<<endl;
if(cj>r[ii][i-1]&&cj<r[ii][i]){
for(auto [x,y]:mpz){
if(x.first!=ii) continue;
if(x.second>r[ii][i-1]&&x.second<r[ii][i]) return;
}
val1=rid[ii][i];
break;
}
}
for(int i=1;i<c[jj].size();i++){
if(ri>c[jj][i-1]&&ri<c[jj][i]){
for(auto [x,y]:mpz){
if(x.second!=jj) continue;
if(x.first>c[jj][i-1]&&x.first<c[jj][i]) return;
}
val2=cid[jj][i];
break;
}
}
// cout<<ri<<" "<<cj<<" "<<val1<<" "<<val2<<endl;
if(val1>0&&val2>0){
add(val1,val2);
}
}
bool rrr[N],ccc[N];
void __(){
cin>>n;
mpd.clear();
mpz.clear();
memset(rrr,0,sizeof rrr);
memset(ccc,0,sizeof ccc);
map<PII,int> mp;
for(int i=1;i<=n;i++){
cin>>d[i].first>>d[i].second;
mp[d[i]]=0;
mpd[d[i]]=i;
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>dd[i].first>>dd[i].second;
mp[dd[i]]=1;
mpz[dd[i]]=1;
}
memset(h,-1,sizeof h);
idx=0;
vector<int> row,col;
map<int,int> mpr,mpc;
row.push_back(-1e9);
col.push_back(-1e9);
for(int i=1;i<=n;i++){
row.push_back(d[i].first);
col.push_back(d[i].second);
}
sort(row.begin(),row.end());
row.erase(unique(row.begin(),row.end()),row.end());
for(int i=1;i<row.size();i++) mpr[row[i]]=i;
sort(col.begin(),col.end());
col.erase(unique(col.begin(),col.end()),col.end());
for(int i=1;i<col.size();i++) mpc[col[i]]=i;
for(int i=1;i<=n;i++){
int t1=mpr[d[i].first],t2=mpc[d[i].second];
r[t1].push_back(d[i].second);
c[t2].push_back(d[i].first);
}
int ridx=0;
for(int i=1;i<=n;i++){
sort(r[i].begin(),r[i].end());
sort(c[i].begin(),c[i].end());
}
// map<PII,int> mr,mc;
for(int i=1;i<=n;i++){
for(auto x:r[i]) {
rid[i].push_back(mpd[{row[i],x}]);
}
}
ridx=0;
for(int i=1;i<=n;i++){
for(auto x:c[i]){
// cout<<col[i]<<" "<<x<<" "<<mpd[{x,col[i]}]<<endl;
cid[i].push_back(mpd[{x,col[i]}]);
}
}
int cnt=0;
for(int i=1;i<row.size();i++){
for(int j=1;j<col.size();j++){
PII zb={row[i],col[j]};
if(!mp.count(zb)){
check(i,row[i],j,col[j]);
}
}
}
n1=n,n2=n;
// cout<<n1<<" "<<n2<<endl;
memset(match,0,sizeof match);
int res=0;
for(int i=1;i<=n;i++){
memset(tf,false,sizeof tf);
// cout<<i<<endl;
if(find(i)) res++;
}
// cout<<res<<endl
vector<PII> ans;
// cout<<n1<<endl;
for(int i=1;i<=n;i++){
// cout<<i<<" "<<match[i]<<endl;
if(match[i]!=0){
PII u=d[match[i]],v=d[i];
// cout<<row[u]<<" "<<col[v]<<endl;
// cout<<u.first<<" "<<u.second<<" "<<v.first<<" "<<v.second<<endl;
// if(mp.count({u.first,v.second})) continue;
rrr[match[i]]=1,ccc[i]=1;
ans.push_back({u.first,v.second});
mp[{u.first,v.second}]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<r[i].size();j++){
bool flag=0;
if(r[i][j]==r[i][j-1]+1){
cout<<-1<<"\n";
return;
}
if(rrr[rid[i][j]]) continue;
for(auto [x,y]:mp){
// if(y==0) continue;
if(x.first!=row[i]) continue;
if(r[i][j-1]<x.second&&r[i][j]>x.second) flag=1;
}
if(!flag){
ans.push_back({row[i],r[i][j-1]+1});
mp[{row[i],r[i][j-1]+1}]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<c[i].size();j++){
bool flag=0;
if(c[i][j]==c[i][j-1]+1){
cout<<-1<<"\n";
return;
}
if(ccc[cid[i][j]]) continue;
for(auto [x,y]:mp){
// if(y==0) continue;
if(x.second!=col[i]) continue;
if(c[i][j-1]<x.first&&c[i][j]>x.first) flag=1;
}
if(!flag){
ans.push_back({c[i][j-1]+1,col[i]});
mp[{c[i][j-1]+1,col[i]}]=1;
}
}
}
cout<<ans.size()<<"\n";
for(auto [x,y]:ans) cout<<x<<" "<<y<<"\n";
}
int main(){
// ios::sync_with_stdio(0);
int _;
cin>>_;
while(_--){
__();
for(int i=0;i<=214;i++) r[i].clear(),c[i].clear();
for(int i=0;i<=214;i++) rid[i].clear(),cid[i].clear();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3980kb
input:
4 7 1 3 6 6 4 7 2 1 6 3 4 1 2 6 3 3 4 6 4 3 1 2 1 1 2 2 0 3 1 1 1 3 3 3 1 1 2 3 1 1 1 3 2 3 0
output:
3 2 3 4 2 3 6 0 1 2 3 -1
result:
wrong answer Participant's answer is 3, but jury has better answer 2 (test case 1)