#include "hundred.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
string ori;
int ans[111][3];
int cnt[3];
map<string,int> ma;
int query(string s)
{
if(ma.find(s)!=ma.end()) return ma[s];
return (ma[s]=Mark(s));
}
vector<string> rem;
bool cmp(pair<char,int> a, pair<char,int> b)
{
return a.se<b.se;
}
int swp(int p1, int p2)
{
int be = query(ori);
swap(ori[p1],ori[p2]);
int af = query(ori);
swap(ori[p1],ori[p2]);
return (af-be);
}
int rs(int p1, int p2, string &ans)
{
int as = 0;
if(ori[p1]==ans[p1]) as--;
if(ori[p2]==ans[p2]) as--;
if(ori[p2]==ans[p1]) as++;
if(ori[p1]==ans[p2]) as++;
return as;
}
vi pos[3];
bool check(string &ss)
{
int rr[3]={0,0,0};
for(int i=0;i<ss.length();i++)
{
if(ss[i]!='?')
{
rr[ss[i]-'A']++;
if(rr[ss[i]-'A']>cnt[ss[i]-'A']) return false;
}
}
return true;
}
std::string GetHundredPoints(int A, int B, int C)
{
//write some "auto-checker" for ez life
cnt[0]=A; cnt[1]=B; cnt[2]=C;
int n=100;
for(int i=0;i<n;i++)
{
ans[i][0]=ans[i][1]=ans[i][2]=1;
}
for(int j=0;j<3;j++)
{
for(int i=0;i<cnt[j];i++)
{
ori+=char('A'+j);
}
}
srand(1203917);
random_shuffle(ori.begin(),ori.end());
vector<pair<char,int> > vv;
for(int i=0;i<3;i++)
{
vv.pb({'A'+i,cnt[i]});
}
sort(vv.begin(),vv.end(),cmp);
int M[3]={0,0,0};
for(int i=0;i<3;i++)
{
M[vv[i].fi-'A']=i;
}
for(int i=0;i<n;i++)
{
pos[M[ori[i]-'A']].pb(i);
}
if(vv[0].se==0)
{
string tmp = "";
for(int i=0;i<n;i++) tmp+="?";
if(vv[1].se==0)
{
string res="";
for(int i=0;i<n;i++) res+=vv[2].fi;
return res;
}
for(int j=1;j<3;j++)
{
tmp[pos[1][0]]=vv[j].fi;
rem.pb(tmp);
}
for(int v:pos[2])
{
int sp = swp(pos[1][0],v);
for(string &r:rem)
{
if(r=="") continue;
int ps=-1;
for(int j=1;j<3;j++)
{
r[v]=vv[j].fi;
if(!check(r))
{
continue;
}
if(rs(pos[1][0],v,r)==sp)
{
ps=j; break;
}
}
if(ps==-1) r="";
else r[v]=vv[ps].fi;
}
}
for(int v:pos[1])
{
int sp = swp(pos[2][0],v);
for(string &r:rem)
{
if(r=="") continue;
int ps=-1;
for(int j=1;j<3;j++)
{
r[v]=vv[j].fi;
if(!check(r))
{
continue;
}
if(rs(pos[2][0],v,r)==sp)
{
ps=j; break;
}
}
if(ps==-1) r="";
else r[v]=vv[ps].fi;
}
}
for(string R:rem)
{
if(R.length()>0) return R;
}
}
else
{
string tmp = "";
for(int i=0;i<n;i++) tmp+="?";
for(int j=0;j<3;j++)
{
tmp[pos[0][0]]=vv[j].fi;
rem.pb(tmp);
}
for(int v:pos[1])
{
int sp = swp(pos[0][0],v);
for(string &r:rem)
{
if(r=="") continue;
int ps=-1;
for(int j=0;j<3;j++)
{
r[v]=vv[j].fi;
if(!check(r))
{
continue;
}
if(rs(pos[0][0],v,r)==sp)
{
ps=j; break;
}
}
if(ps==-1) r="";
else r[v]=vv[ps].fi;
}
}
for(int v:pos[2])
{
int sp = swp(pos[0][0],v);
for(string &r:rem)
{
if(r=="") continue;
int ps=-1;
for(int j=0;j<3;j++)
{
r[v]=vv[j].fi;
if(!check(r))
{
continue;
}
if(rs(pos[0][0],v,r)==sp)
{
ps=j; break;
}
}
if(ps==-1) r="";
else r[v]=vv[ps].fi;
}
}
for(int v:pos[0])
{
int sp = swp(pos[1][0],v);
for(string &r:rem)
{
if(r=="") continue;
int ps=-1;
for(int j=0;j<3;j++)
{
r[v]=vv[j].fi;
if(!check(r))
{
continue;
}
if(rs(pos[1][0],v,r)==sp)
{
ps=j; break;
}
}
if(ps==-1) r="";
else r[v]=vv[ps].fi;
}
}
for(string R:rem)
{
if(R.length()>0&&check(R)) return R;
}
}
}
Compilation message
hundred.cpp: In function 'bool check(std::__cxx11::string&)':
hundred.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<ss.length();i++)
~^~~~~~~~~~~~
hundred.cpp: In function 'std::__cxx11::string GetHundredPoints(int, int, int)':
hundred.cpp:257:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
388 KB |
Output is correct |
| 2 |
Correct |
7 ms |
344 KB |
Output is correct |
| 3 |
Correct |
7 ms |
432 KB |
Output is correct |
| 4 |
Correct |
8 ms |
432 KB |
Output is correct |
| 5 |
Correct |
9 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
388 KB |
Output is correct |
| 2 |
Correct |
7 ms |
344 KB |
Output is correct |
| 3 |
Correct |
7 ms |
432 KB |
Output is correct |
| 4 |
Correct |
8 ms |
432 KB |
Output is correct |
| 5 |
Correct |
9 ms |
384 KB |
Output is correct |
| 6 |
Correct |
6 ms |
384 KB |
Output is correct |
| 7 |
Correct |
8 ms |
396 KB |
Output is correct |
| 8 |
Correct |
7 ms |
344 KB |
Output is correct |
| 9 |
Correct |
8 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
256 KB |
Output is correct |
| 11 |
Correct |
6 ms |
304 KB |
Output is correct |
| 12 |
Correct |
5 ms |
384 KB |
Output is correct |
| 13 |
Correct |
7 ms |
352 KB |
Output is correct |
| 14 |
Correct |
8 ms |
384 KB |
Output is correct |
| 15 |
Correct |
7 ms |
384 KB |
Output is correct |
| 16 |
Correct |
10 ms |
384 KB |
Output is correct |
