QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#610294 | #9412. Stop the Castle | Zaria | WA | 1ms | 3852kb | C++17 | 6.6kb | 2024-10-04 15:30:53 | 2024-10-04 15:30:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define PLL pair<ll,ll>
ll t,n,m;
struct node
{
ll r,c;
bool tag;//0为城堡 1为障碍物
};
struct seg
{
node l,r;
};
struct pair_hash {
template <class T1, class T2>
size_t operator () (const pair<T1,T2> &p) const {
auto h1 = hash<T1>{}(p.first);
auto h2 = hash<T2>{}(p.second);
return h1 ^ h2; // 哈希组合
}
};
struct op{
ll id,val;
bool operator<(const op& a)const{
return this->val > a.val;
}
};
vector<node> row[510],col[510],res;
vector<seg> sg;
ll cnt_r,cnt_c;
unordered_map<ll,ll> hr,hc;
bool st[1010];
bool ok=true;
ll h[1010],ne[1010*2],e[1010*2],idx,di[1010];
bool cmp_r(node a,node b){
return a.c<b.c;
}
bool cmp_c(node a,node b){
return a.r<b.r;
}
void add(ll a,ll b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
node intersect(seg a,seg b){
if(a.l.r==a.r.r&&b.l.r==b.r.r) return{0,0,0};
if(a.l.c==a.r.c&&b.l.c==b.r.c) return{0,0,0};
//a 列 b 行
if(a.l.c==a.r.c&&b.l.r==b.r.r){
a.l.r++,a.r.r--,b.l.c++,b.r.c--;
//if(a.l.r-a.r.r==1||b.l.c-b.r.c==1) return{0,0,0};
if(a.l.c<b.l.c||a.l.c>b.r.c) return{0,0,0};
if(b.l.r<a.l.r||b.l.r>a.r.r) return{0,0,0};
return{b.l.r,a.l.c,0};
}
//a 行 b 列
if(a.l.r==a.r.r&&b.l.c==b.r.c){
a.l.c++,a.r.c--,b.l.r++,b.l.r--;
//if(b.l.r-b.r.r==1||a.l.c-a.r.c==1) return{0,0,0};
if(b.l.c<a.l.c||b.l.c>a.r.c) return{0,0,0};
if(a.l.r<b.l.r||a.l.r>b.r.r) return{0,0,0};
return{a.l.r,b.l.c,0};
}
return{0,0,0};
}
void init(){
//城堡
cin>>n;
for(int i=1;i<=n;i++){
ll r,c;
cin>>r>>c;
//行
if(!hr.count(r)){
hr[r]=++cnt_r;
row[hr[r]].push_back({r,c,0});
}
else{
row[hr[r]].push_back({r,c,0});
}
//列
if(!hc.count(c)){
hc[c]=++cnt_c;
col[hc[c]].push_back({r,c,0});
}
else{
col[hc[c]].push_back({r,c,0});
}
}
//障碍物
cin>>m;
for(int i=1;i<=m;i++){
ll r,c;
cin>>r>>c;
//行
if(!hr.count(r)){
hr[r]=++cnt_r;
row[hr[r]].push_back({r,c,1});
}
else{
row[hr[r]].push_back({r,c,1});
}
//列
if(!hc.count(c)){
hc[c]=++cnt_c;
col[hc[c]].push_back({r,c,1});
}
else{
col[hc[c]].push_back({r,c,1});
}
}
for(int i=1;i<=cnt_r;i++){
sort(row[i].begin(),row[i].end(),cmp_r);
}
for(int i=1;i<=cnt_c;i++){
sort(col[i].begin(),col[i].end(),cmp_c);
}
}
void get_seg(){
//行
for(int i=1;i<=cnt_r;i++){
bool flag=false;
node pre={0,0,0};
for(int j=0;j<row[i].size();j++){
auto d=row[i][j];
if(d.tag==0){
if(flag){
sg.push_back({pre,d});
pre=d;
}
else{
flag=true;
pre=d;
}
}
else{
flag=false;
}
}
}
//列
for(int i=1;i<=cnt_c;i++){
bool flag=false;
node pre={0,0,0};
for(int j=0;j<col[i].size();j++){
auto d=col[i][j];
if(d.tag==0){
if(flag){
sg.push_back({pre,d});
pre=d;
}
else{
flag=true;
pre=d;
}
}
else{
flag=false;
}
}
}
}
void clear(){
for(int i=1;i<=cnt_r;i++) row[i].clear();
for(int i=1;i<=cnt_c;i++) col[i].clear();
for(int i=1;i<=1000;i++) st[i]=false;
sg.clear();
hr.clear();
hc.clear();
cnt_c=cnt_r=0;
res.clear();
ok=true;
}
void get_res(){
unordered_set<PLL,pair_hash> ss;
ll len=sg.size();
idx=0;
for(int i=0;i<len;i++) h[i]=-1,di[i]=0,st[i]=0;
//存图
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
if(i==j) continue;
auto d=intersect(sg[i],sg[j]);
if(d.r!=0||d.c!=0){
ll x=i,y=j;
if(x>y) swap(x,y);
if(!ss.count({x,y})){
add(x,y),add(y,x);
di[x]++,di[y]++;
ss.insert({x,y});
}
}
}
}
//找出最优方案
priority_queue<op> q;
vector<PLL> re;
for(int i=0;i<len;i++) q.push({i,di[i]});
while(q.size()){
auto d=q.top();
if(d.val==0){
q.pop();
re.push_back({d.id,-1});
}
else{
if(st[d.id]){
q.pop();
continue;
}
ll u=-1;
st[d.id]=true;
ll ma=-1;
for(int i=h[d.id];~i;i=ne[i]){
int j=e[i];
if(!st[j]){
if(ma<di[u]) u=j,ma=di[u];
}
}
if(u!=-1) st[u]=true;
re.push_back({d.id,u});
q.pop();
}
}
//求点
for(int i=0;i<re.size();i++){
auto dd=re[i];
if(dd.second==-1){
auto d=sg[dd.first];
//为行
if(d.l.r==d.r.r){
if(d.l.c+1==d.r.c){
ok=false;
}
else{
res.push_back({d.l.r,d.l.c+1,0});
}
}
//为列
if(d.l.c==d.r.c){
if(d.l.r+1==d.r.r){
ok=false;
}
else{
res.push_back({d.l.r+1,d.l.c,0});
}
}
}
else{
auto d=intersect(sg[dd.first],sg[dd.second]);
res.push_back({d.r,d.c,0});
}
}
}
int main(){
cin>>t;
while(t--){
init();//读入数据并排序
get_seg();//将数据处理成需要隔断的线段
get_res();//得到答案
if(ok){
cout<<res.size()<<endl;
for(auto d:res){
cout<<d.r<<' '<<d.c<<endl;
}
}
else{
cout<<-1<<endl;
}
clear();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3624kb
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: 0
Accepted
time: 1ms
memory: 3852kb
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 29 38 34 18 5 16 10 12 6 34 50 16 15 20 26 0 1 16 10 0 1 43 22 5 1 3 33 10 42 44 1 13 44 45 0 5 27 41 44 4 21 15 29 26 8 1 1 32 9 0 0 0 0 6 12 11 23 44 24 46 29 21 23 10 35 34 0 3 20 30 43 25 31 17 0 -1 3 25 7 17 39 16 36 6 5 5 7 3 8 10 4 9 6 4 2 11
result:
ok ok 21 cases (21 test cases)
Test #3:
score: 0
Accepted
time: 1ms
memory: 3632kb
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:
46 35 276 224 393 390 308 440 179 453 251 286 367 278 272 271 186 311 455 138 429 415 305 240 35 187 433 277 189 52 67 38 25 39 477 261 468 274 67 57 139 19 436 21 499 11 4 380 385 311 177 126 275 199 432 154 496 187 467 306 374 52 139 393 307 260 223 334 367 352 61 349 112 280 186 224 147 185 35 27...
result:
ok ok 2 cases (2 test cases)
Test #4:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
20 13 89287395 441913071 89287395 590314987 142917372 582720391 142917372 598813561 232930851 582720391 263974835 468188689 263974835 490702144 543529670 152471388 543529670 219371706 647691663 598813561 772865038 598813561 773363571 482933265 773363571 561453301 8 128947560 120560639 264980960 4742...
output:
8 89287395 441913072 263974835 468188690 142917373 598813561 142917373 582720391 647691664 598813561 773363571 482933266 142917372 582720392 543529670 152471389 7 808969359 386523246 808969359 891229782 469117951 762966373 59832704 871951216 92745430 358274214 808969360 354711322 808969359 818037531...
result:
ok ok 20 cases (20 test cases)
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3852kb
input:
2 184 35763790 435860426 152681166 443483111 261932524 745277126 261932524 787982418 314305867 342102981 314305867 522593781 314305867 747023891 314305867 811404535 314305867 816914009 314305867 857896659 319901983 797458033 321347896 342102981 332550928 902179526 343207116 914408792 350635050 15515...
output:
160 261932524 745277127 314305867 522593782 350635050 155155062 673102149 351421769 702209412 342102981 716861004 342102981 730593612 342102981 712954987 342102981 673102149 356915105 638591122 342102981 673102150 342102981 611662527 342102981 620290597 342102981 496813081 751818165 673102149 342102...
result:
wrong answer Participant's answer is 137, but jury has better answer 136 (test case 2)