E

Dorijanko

Oct 11th, 2023

106

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

text 1.89 KB | None | 0 0

raw download clone embed print report

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
int n,mad;
int ko(string a,string b)
{
int cn=0;
for (int i=0;i<8;++i) if (a[i]==b[i]) ++cn;
return cn;
}
map<vector<string>,string> koj;
void nap(vector<string> v,int d)
{
if (v.size()<=1)
{
mad=max(mad,d+(int)v.size());
return;
}
random_shuffle(v.begin(),v.end());
ld maxsl=-1;
string kak="??";
for (auto x: v)
{
vi u(9);
for (auto y: v) ++u[ko(x,y)];
ld s=0;
for (auto y: u) s+=log(y+1);
if (s>maxsl)
{
maxsl=s;
kak=x;
}
}
vector<vector<string>> u(9);
for (auto y: v) u[ko(kak,y)].pb(y);
for (int i=0;i<8;++i) nap(u[i],d+1);
koj[v]=kak;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(2130);
vector<string> v;
for (int b=0;b<(1<<24);++b) //QKRBN
{
vi cn(8);
for (int i=0;i<8;++i) ++cn[(b>>(i*3))&7];
if (cn[0]!=1 || cn[1]!=1 || cn[2]!=2 || cn[3]!=2 || cn[4]!=2) continue;
int p1=-1,p2=-1;
for (int i=0;i<8;++i) if (((b>>(i*3))&7)==3)
{
if (p1==-1) p1=i;
else p2=i;
}
if ((p1+p2)%2==0) continue;
p1=-1,p2=-1;
for (int i=0;i<8;++i) if (((b>>(i*3))&7)==2)
{
if (p1==-1) p1=i;
else p2=i;
}
bool ok=1;
for (int i=0;i<8;++i) if (((b>>(i*3))&7)==1)
{
if (i<p1 || i>p2) ok=0;
}
string s,u="QKRBN";
for (int i=0;i<8;++i) s.pb(u[(b>>(i*3))&7]);
if (ok) v.pb(s);
}
for (int i=0;i<100;++i)
{
srand(i);
mad=0;
nap(v,0);
cout<<i<<' '<<mad<<endl;
}
exit(0);
while (1)
{
string w;
cin>>w;
if (w=="END") exit(0);
int c;
cin>>c;
auto mog=v;
while (mog.size()>1)
{
}
}
}

Add Comment

Please, Sign In to add comment