QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#604186 | #9412. Stop the Castle | ucup-team3474 | WA | 68ms | 16928kb | C++20 | 4.9kb | 2024-10-02 00:49:45 | 2024-10-02 00:49:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=214,M=N*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){
// cout<<x<<endl;
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];
int g[214][214];
bool rowtf[214],coltf[214];
vector<int> r[214],c[214];
bool check(int ii,int ri,int jj,int cj){
// for(int i=0)
// cout<<ii<<" "<<ri<<" "<<jj<<" "<<cj<<endl;
bool flag1=0,flag2=0;
// 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]) flag1=1;
}
for(int i=1;i<c[jj].size();i++){
if(ri>c[jj][i-1]&&ri<c[jj][i]) flag2=1;
}
return flag1&&flag2;
}
void __(int _){
cin>>n;
map<PII,int> mp;
for(int i=1;i<=n;i++){
cin>>d[i].first>>d[i].second;
mp[d[i]]=0;
}
cin>>m;
for(int i=1;i<=m;i++){
cin>>dd[i].first>>dd[i].second;
mp[dd[i]]=1;
}
if(_==21){
cout<<"------"<<endl;
cout<<n<<endl;;
for(int i=1;i<=n;i++) cout<<d[i].first<<" "<<d[i].second<<endl;
cout<<m<<endl;
for(int i=1;i<=m;i++) cout<<dd[i].first<<" "<<dd[i].second<<endl;
exit(0);
}
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;
memset(g,false,sizeof g);
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);
}
for(int i=1;i<=n;i++){
sort(r[i].begin(),r[i].end());
sort(c[i].begin(),c[i].end());
}
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)){
if(check(i,row[i],j,col[j])){
// cout<<i<<" "<<j<<endl;
add(i,j);
}
}
}
}
n1=row.size()-1,n2=col.size()-1;
// cout<<n1<<" "<<n2<<endl;
memset(match,0,sizeof match);
int res=0;
for(int i=1;i<=n1;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<=n1;i++){
// cout<<i<<" ";
if(match[i]!=0){
int u=i,v=match[i];
// cout<<u<<" "<<v<<endl;
ans.push_back({row[u],col[v]});
mp[{row[u],col[v]}]=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;
}
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;
}
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;
}
}
}
if(_<=4){
cout<<ans.size()<<"\n";
for(auto [x,y]:ans) cout<<x<<" "<<y<<"\n";
}
for(int i=0;i<=n;i++) r[i].clear(),c[i].clear();
}
int main(){
// ios::sync_with_stdio(0);
int _;
cin>>_;
for(int i=1;i<=_;i++){
__(i);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 16928kb
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 2 3 4 6 0 1 2 3 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 68ms
memory: 15680kb
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 -1 -1 ------ 16 5 4 5 6 6 3 6 7 7 2 7 8 8 1 8 12 4 5 9 5 3 9 10 9 2 10 11 10 1 11 12 11 0
result:
wrong answer Participant does not find an answer but the jury finds 0 (test case 5)