QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#604238 | #9412. Stop the Castle | ucup-team3474 | WA | 1ms | 4056kb | C++20 | 5.4kb | 2024-10-02 02:19:55 | 2024-10-02 02:19:56 |
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;
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]) val1=rid[ii][i];
}
for(int i=1;i<c[jj].size();i++){
if(ri>c[jj][i-1]&&ri<c[jj][i]) val2=cid[jj][i];
}
// cout<<ri<<" "<<cj<<" "<<val1<<" "<<val2<<endl;
if(val1>0&&val2>0){
add(val1,val2);
}
}
bool rrr[N],ccc[N];
void __(){
cin>>n;
mpd.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;
}
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;
}
}
if(n>100){
cout<<ans.size()<<endl;
exit(0);
}
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();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3952kb
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:
2 4 6 2 3 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
21 11 3 5 18 6 19 12 27 48 28 38 30 12 33 18 42 18 43 38 45 46 48 34 3 2 6 24 4 41 45 15 11 6 15 27 16 9 16 14 16 48 19 26 25 12 27 26 28 4 31 40 32 6 33 50 37 50 46 11 50 29 17 1 49 4 9 9 15 9 22 11 31 11 46 14 28 17 5 17 49 18 43 20 31 30 46 33 11 33 33 34 15 36 6 47 10 2 16 46 36 30 11 7 34 7 41 ...
output:
3 20 12 34 18 29 38 5 16 10 16 15 12 6 20 26 34 50 0 1 16 10 0 1 43 22 5 1 3 1 13 33 10 44 45 42 44 0 5 27 41 29 26 44 4 8 1 21 15 1 32 9 0 0 0 0 6 23 10 35 34 12 11 23 44 29 21 24 46 0 3 20 30 43 25 31 17 0 -1 3 16 36 25 7 17 39 6 5 5 8 11 6 4 7 3 4 9 3 10
result:
ok ok 21 cases (21 test cases)
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 4056kb
input:
2 200 7 52 9 160 10 4 12 61 18 436 19 430 20 499 24 139 25 416 29 53 33 153 35 275 35 310 37 25 38 477 39 349 42 120 44 158 45 330 49 486 50 204 51 67 52 138 52 305 56 139 63 132 66 4 67 327 70 484 71 67 72 308 74 218 76 479 81 139 82 90 86 201 87 335 91 35 91 220 92 496 94 29 94 436 96 359 97 299 1...
output:
20
result:
wrong output format Unexpected end of file - int32 expected (test case 1)