結果
問題 | No.1121 Social Distancing in Cinema |
ユーザー |
![]() |
提出日時 | 2020-07-26 16:39:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,920 bytes |
コンパイル時間 | 1,239 ms |
コンパイル使用メモリ | 125,944 KB |
最終ジャッジ日時 | 2025-01-12 06:03:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 41 WA * 6 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#include <utility>#include <functional>#include <time.h>#include <stack>#include <array>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<int, int> P;/*const ll INF=1e18;struct edge {int to; ll cap; int rev;} ;vector<edge> G[202];int level[202];int iter[202];void add_edge(int from, int to, ll cap){edge e;e.to=to, e.cap=cap, e.rev=G[to].size();G[from].push_back(e);e.to=from, e.cap=0, e.rev=G[from].size()-1;G[to].push_back(e);}void bfs(int s){memset(level, -1, sizeof(level));queue<int> que;level[s]=0;que.push(s);while(!que.empty()){int v=que.front();que.pop();for(int i=0; i<G[v].size(); i++){edge e=G[v][i];if(e.cap>0 && level[e.to]<0){level[e.to]=level[v]+1;que.push(e.to);}}}}ll dfs(int v, int t, ll f){if(v==t) return f;for(int &i=iter[v]; i<G[v].size(); i++){edge &e=G[v][i];if(e.cap>0 && level[v]<level[e.to]){ll d=dfs(e.to, t, min(f, e.cap));if(d>0){e.cap-=d;G[e.to][e.rev].cap+=d;return d;}}}return 0;}ll max_flow(int s, int t){ll flow=0;while(1){bfs(s);if(level[t]<0) return flow;memset(iter, 0, sizeof(iter));ll f;while((f=dfs(s, t, INF))>0){flow+=f;}}}*/int p[90]={5,35,25,16,15,0,24,14,3,4,6,7,17,18,27,26,11,1,2,12,32,9,28,19,29,36,33,22,23,13,8,43,45,42,39,44,54,64,31,34,37,55,65,53,52,56,66,76,10,57,46,47,67,77,62,68,78,63,69,21,38,58,59,73,75,60,50,74,30,20,48,49,81,82,83,84,88,61,40,41,85,86,87,79,89,80,70,71,72,51};int q[90]={0,50,60,80,81,82,83,84,85,86,10,70,61,71,72,73,74,75,76,77,20,1,2,3,4,5,6,7,87,78,30,11,12,13,14,15,16,17,8,88,40,21,22,23,24,25,26,27,18,9,31,41,32,33,34,35,36,37,28,19,51,42,52,43,44,45,46,47,38,29,62,53,63,54,64,55,56,57,48,39,65,66,67,58,68,49,59,69,79,89};int num[510][504];int main(){for(int i=0; i<10; i++) for(int j=0; j<9; j++) num[i][j]=j*10+i;for(int i=0; i<500/10; i++){for(int x=0; x<10; x++){for(int y=0; y<9; y++){int x1=q[y*10+x]%10, y1=q[y*10+x]/10;num[(i+1)*10+x1][y1]=num[i*10+x][y];}}for(int j=0; j<504/9-1; j++){for(int x=0; x<10; x++){for(int y=0; y<9; y++){int x1=p[y*10+x]%10, y1=p[y*10+x]/10;num[i*10+x1][(j+1)*9+y1]=num[i*10+x][j*9+y];}}}}int n; cin>>n;vector<int> v[90];for(int i=0; i<n; i++){int x, y; cin>>x>>y;x--; y--;v[num[x][y]].push_back(i);}for(int i=0; i<90; i++){if(v[i].size()>=(n+89)/90){cout<<v[i].size()<<endl;for(auto k:v[i]) cout<<k+1<<" ";cout<<endl;return 0;}}/*int s=180, t=s+1;for(int i=0; i<90; i++){add_edge(s, i, 1), add_edge(i+90, t, 1);}for(int i=0; i<10; i++){for(int j=0; j<9; j++){for(int k=0; k<10; k++){for(int l=0; l<9; l++){int d=(i-k)*(i-k)+(9+l-j)*(9+l-j);if(d>=100) add_edge(j*10+i, l*10+k+90, 1);}}}}max_flow(s, t);for(int i=0; i<90; i++){for(auto e:G[i]){if(e.to==s) continue;if(e.cap==0){p[i]=e.to-90;}}}for(int i=0; i<202; i++){G[i].clear(); level[i]=iter[i]=0;}for(int i=0; i<90; i++){add_edge(s, i, 1), add_edge(i+90, t, 1);}for(int i=0; i<10; i++){for(int j=0; j<9; j++){for(int k=0; k<10; k++){for(int l=0; l<9; l++){int d=(i-10-k)*(i-10-k)+(l-j)*(l-j);if(d>=100) add_edge(j*10+i, l*10+k+90, 1);}}}}max_flow(s, t);for(int i=0; i<90; i++){for(auto e:G[i]){if(e.to==s) continue;if(e.cap==0){q[i]=e.to-90;}}}*/return 0;}