結果

問題 No.1121 Social Distancing in Cinema
ユーザー chocoruskchocorusk
提出日時 2020-07-26 16:39:39
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
J_TLE  
実行時間 -
コード長 3,932 bytes
コンパイル時間 5,630 ms
コンパイル使用メモリ 159,336 KB
最終ジャッジ日時 2025-01-12 06:04:21
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 41 WA * 5 J_TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_popcount
using 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;
}
}
assert(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0