제출 #473502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
473502		Ahmadsm2005	Genetics (BOI18_genetics)	C++17	100 / 100	1478 ms	37540 KiB

genetics

#include <bits/stdc++.h>
#define endl '\n'
#define modulo 998244353
#define modulo2 998244353
#define eps 0.00000001
#define int long long
//#define int __int16_t
#define PI acos(-1)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")
#define sinDegrees(x) sin((x) * PI / 180.0)
#define cosDegrees(x) cos((x) * PI / 180.0)
#define tanDegrees(x) tan((x) * PI / 180.0)
#define atanDegrees(x) atan(x)* 180.0 / PI
#define asinDegrees(x) asin(x)* 180.0 / PI
#define EPS 0.000000001
using namespace std;
int power(int x,int y,int m=modulo)
{
if(y<0)
return 0;
int temp;
if(y == 0)
return 1;
temp = (power(x, y/2,m))%m;
if (y%2 == 0)
return ((temp%m)*temp)%m;
else
return ((x*temp%m)*temp%m)%m;
}
int inv(int x,int m=modulo)
{
return (power(x,m-2,m))%m;
}
int n,m,k;
bool BAD[4100],GOOD[4100][4100];
string s;
int lolz[4100];
unsigned long long wow[4100][65],wow2[4100][65],TEMP[65];
int GETA(int x,int y){
int CNT=0;
for(int i=0;i<65;i++){
CNT+=__builtin_popcountll((wow[x][i]^wow[y][i])|(wow2[x][i]^wow2[y][i]));
}
return CNT;
}
int32_t main()
{
cin.tie(0),iostream::sync_with_stdio(0);
//freopen("halfnice.in","r",stdin);
cin>>n>>m>>k;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
for(int i=0;i<n;i++){
cin>>s;
lolz[i]=i;
for(int l=0;l<m;l++){
int Q=((unsigned long long)1<<l%64);
if(s[l]=='C')
wow[i][l/64]|=Q;
else if(s[l]=='T')
wow2[i][l/64]|=Q;
else if(s[l]=='G')
wow[i][l/64]|=Q,wow2[i][l/64]|=Q;
}
}
while(1){
shuffle(lolz,lolz+n,rng);
if(BAD[lolz[0]])
continue;
for(int i=1;i<n;i++){
if(GOOD[lolz[0]][lolz[i]])
continue;
if(GETA(lolz[0],lolz[i])!=k){
BAD[lolz[0]]=1,BAD[lolz[i]]=1;
goto a;
}
else
GOOD[lolz[0]][lolz[i]]=1,GOOD[lolz[i]][lolz[0]]=1;
}
cout<<lolz[0]+1<<endl;
break;
a:;
}
}

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26