結果
問題 | No.1121 Social Distancing in Cinema |
ユーザー |
|
提出日時 | 2020-07-24 04:07:33 |
言語 | C (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,669 bytes |
コンパイル時間 | 359 ms |
コンパイル使用メモリ | 31,488 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-24 05:51:23 |
合計ジャッジ時間 | 9,213 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 WA * 22 |
ソースコード
#include<stdio.h>#include<stdbool.h>int q[1048576];int qp=0,qqp=0;void qpush(int x){qp++;q[qp]=x;}int qpop(){qqp++;return q[qqp];}int dsc[512][512]={0};int sid[512][512];int res[524288],rc=0;bool isvalid(int a,int b){if(a<0||a>500){return false;}if(b<0||b>500){return false;}return true;}void rem(int a,int b){if(sid[a][b]==-1){return;}sid[a][b]=-1;int i,j,x,y;for(i=-10;i<=10;i++){for(j=-10;j<=10;j++){if((i*i+j*j)>=100){continue;}x=a+i;y=b+j;if(isvalid(x,y)){if(sid[x][y]!=-1){dsc[x][y]--;if(dsc[x][y]<=89){dsc[x][y]=1000000007;qpush(x*512+y);}}}}}}void sit(int a,int b){if(sid[a][b]==-1){return;}res[rc]=sid[a][b];rc++;int i,j,x,y;for(i=-10;i<=10;i++){for(j=-10;j<=10;j++){if((i*i+j*j)>=100){continue;}x=a+i;y=b+j;if(isvalid(x,y)){rem(x,y);}}}}int main(){int i,j,k,n,a,b,x,y;for(i=0;i<512;i++){for(j=0;j<512;j++){sid[i][j]=-1;}}scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&a,&b);sid[a][b]=i;for(j=-10;j<=10;j++){for(k=-10;k<=10;k++){if((j*j+k*k)>=100){continue;}x=a+j;y=b+k;if(isvalid(x,y)){dsc[x][y]++;}}}dsc[a][b]--;}for(i=0;i<512;i++){for(j=0;j<512;j++){if(sid[i][j]!=-1 && dsc[i][j]<=89){dsc[i][j]=1000000007;qpush(i*512+j);}}}while(qp!=qqp){x=qpop();sit(x/512,x%512);}printf("%d\n",rc);for(i=0;i<rc;i++){if(i){printf(" ");}printf("%d",res[i]);}printf("\n");}