#518833 (C++17) No.1121 Social Distancing in Cinema

提出ソース

結果

問題	No.1121 Social Distancing in Cinema
ユーザー	chocorusk
提出日時	2020-07-26 16:39:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	3,920 bytes
コンパイル時間	1,549 ms
コンパイル使用メモリ	128,988 KB
実行使用メモリ	5,884 KB
最終ジャッジ日時	2023-09-11 03:00:21
合計ジャッジ時間	8,411 ms
ジャッジサーバーID （参考情報）	judge11 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 4,432 KB
testcase_01	AC	3 ms 4,384 KB
testcase_02	AC	3 ms 4,404 KB
testcase_03	AC	3 ms 4,376 KB
testcase_04	AC	3 ms 4,380 KB
testcase_05	AC	3 ms 4,384 KB
testcase_06	AC	3 ms 4,440 KB
testcase_07	AC	3 ms 4,428 KB
testcase_08	AC	2 ms 4,392 KB
testcase_09	AC	3 ms 4,380 KB
testcase_10	AC	3 ms 4,388 KB
testcase_11	AC	3 ms 4,388 KB
testcase_12	AC	3 ms 4,508 KB
testcase_13	AC	3 ms 4,416 KB
testcase_14	AC	4 ms 4,380 KB
testcase_15	AC	5 ms 4,412 KB
testcase_16	AC	13 ms 4,632 KB
testcase_17	AC	45 ms 4,892 KB
testcase_18	AC	84 ms 5,724 KB
testcase_19	AC	97 ms 5,884 KB
testcase_20	AC	6 ms 4,412 KB
testcase_21	WA	-
testcase_22	AC	5 ms 4,668 KB
testcase_23	AC	3 ms 4,380 KB
testcase_24	AC	3 ms 4,376 KB
testcase_25	WA	-
testcase_26	AC	35 ms 4,784 KB
testcase_27	AC	4 ms 4,380 KB
testcase_28	AC	85 ms 5,680 KB
testcase_29	AC	33 ms 4,648 KB
testcase_30	AC	26 ms 4,812 KB
testcase_31	AC	97 ms 5,884 KB
testcase_32	AC	74 ms 5,748 KB
testcase_33	AC	33 ms 4,604 KB
testcase_34	AC	33 ms 4,828 KB
testcase_35	AC	78 ms 5,384 KB
testcase_36	AC	94 ms 5,768 KB
testcase_37	AC	24 ms 5,064 KB
testcase_38	AC	38 ms 4,952 KB
testcase_39	AC	84 ms 5,612 KB
testcase_40	AC	20 ms 4,860 KB
testcase_41	WA	-
testcase_42	WA	-
testcase_43	WA	-
testcase_44	AC	93 ms 5,556 KB
testcase_45	AC	93 ms 5,768 KB
testcase_46	WA	-
testcase_47	AC	3 ms 4,388 KB
testcase_48	AC	3 ms 4,432 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
		}
	}
	/*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;
}

yukicoder

結果

テストケース

ソースコード