結果
問題 | No.1121 Social Distancing in Cinema |
ユーザー |
![]() |
提出日時 | 2020-07-22 23:13:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,279 bytes |
コンパイル時間 | 2,058 ms |
コンパイル使用メモリ | 186,988 KB |
実行使用メモリ | 7,680 KB |
最終ジャッジ日時 | 2024-06-23 00:46:40 |
合計ジャッジ時間 | 7,369 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 46 WA * 1 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long #define REP(i,m,n) for(int i=(m);i<(n);i++) #define rep(i,n) REP(i,0,n) #define pb push_back #define all(a) a.begin(),a.end() #define rall(c) (c).rbegin(),(c).rend() #define mp make_pair #define endl '\n' #define vec vector<ll> #define mat vector<vector<ll> > #define fi first #define se second typedef long long ll; typedef pair<ll,ll> pll; typedef long double ld; const ll inf=1e9+7; const ll mod=998244353; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; signed main(){ ll n;cin>>n; vector<vector<ll> >a(500,vector<ll>(500)); rep(i,n){ ll x,y;cin>>x>>y; x--;y--; a[x][y]=i+1; } vector<vector<ll> >used(500,vector<ll>(500)); vector<ll>ans1(0); vector<ll>ans2(0); vector<ll>ans3(0); vector<ll>ans4(0); ll s=(n-1)/90+1; rep(i,500){ rep(j,500){ if(used[i][j])continue; if(a[i][j]==0)continue; ans1.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } rep(i,500){ rep(j,500)used[i][j]=0; } rep(j,500){ rep(i,500){ if(used[i][j])continue; if(a[i][j]==0)continue; ans2.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } rep(i,500){ rep(j,500)used[i][j]=0; } for(int i=499;i>=0;i--){ for(int j=499;j>=0;j--){ if(used[i][j])continue; if(a[i][j]==0)continue; ans3.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } rep(i,500){ rep(j,500)used[i][j]=0; } for(int j=499;j>=0;j--){ for(int i=499;i>=0;i--){ if(used[i][j])continue; if(a[i][j]==0)continue; ans4.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } vector<ll>ans11(0); vector<ll>ans21(0); vector<ll>ans31(0); vector<ll>ans41(0); rep(i,500){ rep(j,500)used[i][j]=0; } rep(i,500){ for(int j=499;j>=0;j--){ if(used[i][j])continue; if(a[i][j]==0)continue; ans11.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } rep(i,500){ rep(j,500)used[i][j]=0; } rep(j,500){ for(int i=499;i>=0;i--){ if(used[i][j])continue; if(a[i][j]==0)continue; ans21.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } rep(i,500){ rep(j,500)used[i][j]=0; } for(int i=499;i>=0;i--){ rep(j,500){ if(used[i][j])continue; if(a[i][j]==0)continue; ans31.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } rep(i,500){ rep(j,500)used[i][j]=0; } for(int j=499;j>=0;j--){ rep(i,500){ if(used[i][j])continue; if(a[i][j]==0)continue; ans41.pb(a[i][j]); used[i][j]=1; queue<pll>q; q.push(mp(i,j)); while(!q.empty()){ pll k=q.front(); q.pop(); ll x=k.first; ll y=k.second; rep(l,4){ ll nx=x+dx[l]; ll ny=y+dy[l]; if(nx<0||nx>=500||ny<0||ny>=500)continue; if((nx-i)*(nx-i)+(ny-j)*(ny-j)>=100)continue; if(used[nx][ny])continue; q.push(mp(nx,ny)); used[nx][ny]=1; } } } } cout<<s<<endl; if(ans1.size()>=s){ rep(i,s){ cout<<ans1[i]<<' '; } }else if(ans2.size()>=s){ rep(i,s){ cout<<ans2[i]<<' '; } }else if(ans3.size()>=s){ rep(i,s){ cout<<ans3[i]<<' '; } }else if(ans4.size()>=s){ rep(i,s){ cout<<ans4[i]<<' '; } }else if(ans11.size()>=s){ rep(i,s){ cout<<ans11[i]<<' '; } }else if(ans21.size()>=s){ rep(i,s){ cout<<ans21[i]<<' '; } }else if(ans31.size()>=s){ rep(i,s){ cout<<ans31[i]<<' '; } }else if(ans41.size()>=s){ rep(i,s){ cout<<ans41[i]<<' '; } } cout<<endl; }