Submission #1253326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253326		kuailededatong	메시지 (IOI24_message)	C++20	100 / 100	374 ms	860 KiB

message

#include"message.h"
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<unordered_map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<array>
#include<tuple>
#include<ctime>
#include<random>
#include<cassert>
#include<chrono>
#define x1 xx1
#define y1 yy1
#define IOS ios::sync_with_stdio(false)
#define ITIE cin.tie(0)
#define OTIE cout.tie(0)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define gc getchar
#define pc putchar
#define pb emplace_back
#define un using namespace
#define il inline
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof x)
#define popc __builtin_popcountll
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) ((x)&-(x))
#define lson(x) ((x)<<1)
#define rson(x) ((x)<<1|1)
//#define double long double
//#define int long long
//#define int __int128
using namespace std;
using i64=long long;
using u64=unsigned long long;
using pii=pair<int,int>;
template<typename T1,typename T2>inline void ckmx(T1 &x,T2 y){x=x>y?x:y;}
template<typename T1,typename T2>inline void ckmn(T1 &x,T2 y){x=x<y?x:y;}
inline auto rd(){
	int qwqx=0,qwqf=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')qwqf=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){qwqx=(qwqx<<1)+(qwqx<<3)+ch-48;ch=getchar();}return qwqx*qwqf;
}
template<typename T>inline void write(T qwqx,char ch='\n'){
	if(qwqx<0){qwqx=-qwqx;putchar('-');}
	int qwqy=0;static char qwqz[40];
	while(qwqx||!qwqy){qwqz[qwqy++]=qwqx%10+48;qwqx/=10;}
	while(qwqy--){putchar(qwqz[qwqy]);}if(ch)putchar(ch);
}
const int mod=998244353;
template<typename T1,typename T2>inline void adder(T1 &x,T2 y){x+=y,x=x>=mod?x-mod:x;}
template<typename T1,typename T2>inline void suber(T1 &x,T2 y){x-=y,x=x<0?x+mod:x;}
const int maxn=31,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
const int S=1025;
void send_message(vector<bool>M,vector<bool>C){
	M.pb(1);
	while((int)M.size()<S)M.pb(0);
	vector<bool>EMPTY(31,0);
	vector<vector<bool>>A(66,EMPTY);
	int cnt=0;
	rep(j,0,30){
		int p;
		for(p=1;p<=30&&C[(j+p)%31];p++);
		rep(i,0,p-1){
			if(i==p-1)A[i][j]=1;
			else A[i][j]=0;
		}
		if(!C[j]){
			rep(i,p,65)A[i][j]=M[cnt++];
		}
	}
	assert(cnt==S);
	rep(i,0,65)send_packet(A[i]);
}
vector<pii>G[maxn];
bool c[maxn];
bool vis[maxn];
vector<int>rg;
int pre[maxn];
void dfs(int x,int e){
	vis[x]=1;
	for(pii _:G[x]){
		int u=_.fi,id=_.se;
		if(id==e)continue;
		if(vis[u]){
			if(!rg.empty())continue;
			int p=x;
			while(p^u)rg.pb(p),p=pre[p];
			rg.pb(u);
		}else{
			pre[u]=x,dfs(u,id);
		}
	}
}
vector<bool>receive_message(vector<vector<bool>>R){
	mem(vis,0),mem(c,0),mem(pre,-1); 
	rep(i,0,30)G[i].clear();
	vector<int>P(31,0);
	int edges=0;
	rep(i,0,30){
		rep(j,0,65){
			P[i]++;
			if(R[j][i])break;
		}
		++edges,G[i].pb(mp((i+P[i])%31,edges)),G[(i+P[i])%31].pb(mp(i,edges));
	}
	rep(i,0,30)if(!vis[i]){
		rg.clear(),dfs(i,-1);
		if(rg.size()==16){
			for(int u:rg)c[u]=1;
			break;
		}
	}
	vector<bool>M;
	rep(i,0,30)if(c[i]){
		rep(j,P[i],65)M.pb(R[j][i]);
	}
	assert(M.size()==S);
	while(!M.back())M.pop_back();
	M.pop_back();
	return M;
}
/*
g++ qoj9237.cpp grader.cpp -o a -std=c++14 -O2
*/

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90