QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#610204 | #9412. Stop the Castle | Zaria | WA | 1ms | 3784kb | C++17 | 6.4kb | 2024-10-04 15:14:57 | 2024-10-04 15:14: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);
ss.insert({x,y});
}
}
}
}
//找出最优方案
//priority_queue<op> q;
vector<PLL> re;
for(int i=0;i<len;i++){
if(!st[i]){
bool flag=false;
for(int j=h[i];~j;j=ne[j]){
int jj=e[j];
if(!st[jj]){
st[i]=st[jj]=true;
re.push_back({i,jj});
flag=true;
break;
}
}
if(!flag){
re.push_back({i,-1});
st[i]=true;
}
}
}
//求点
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: 3784kb
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: 3628kb
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 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 12 11 23 10 23 44 29 21 35 34 24 46 0 3 20 30 43 25 31 17 0 -1 3 16 36 25 7 17 39 6 5 5 6 4 7 3 8 11 4 9 3 10
result:
ok ok 21 cases (21 test cases)
Test #3:
score: -100
Wrong Answer
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:
51 35 276 52 275 91 138 94 35 126 67 126 214 132 305 154 153 154 467 185 147 187 433 187 453 199 356 224 374 224 393 260 223 261 468 270 187 274 67 277 189 277 273 306 368 311 177 311 455 334 367 349 112 352 186 390 308 393 307 440 179 453 251 10 160 11 4 13 61 312 61 19 436 21 499 25 139 57 139 38 ...
result:
wrong answer Participant's answer is 51, but jury has better answer 46 (test case 1)