This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
string calc(vector<int> arr,string S){
int N = S.size();
string res(N,'$');
for(int i=0;i<N-1;i++){
if(arr[i])continue;
{
vector<bool> present(3);
if(S[i]=='R')present[0]=true;
else if(S[i]=='G')present[1]=true;
else if(S[i]=='B')present[2]=true;
if(S[i+1]=='R')present[0]=true;
else if(S[i+1]=='G')present[1]=true;
else if(S[i+1]=='B')present[2]=true;
if(!present[0])res[i]=res[i+1]='R';
else if(!present[1])res[i]=res[i+1]='G';
else if(!present[2])res[i]=res[i+1]='B';
}
for(int j=i-1;j>=0;j--){
if(arr[j]!=1)break;
vector<bool> present(3);
if(S[j]=='R')present[0]=true;
else if(S[j]=='G')present[1]=true;
else if(S[j]=='B')present[2]=true;
if(res[j+1]=='R')present[0]=true;
else if(res[j+1]=='G')present[1]=true;
else if(res[j+1]=='B')present[2]=true;
if(!present[0])res[j]='R';
else if(!present[1])res[j]='G';
else if(!present[2])res[j]='B';
}
for(int j=i+2;j<N;j++){
if(arr[j-1]!=1)break;
vector<bool> present(3);
if(S[j]=='R')present[0]=true;
else if(S[j]=='G')present[1]=true;
else if(S[j]=='B')present[2]=true;
if(res[j-1]=='R')present[0]=true;
else if(res[j-1]=='G')present[1]=true;
else if(res[j-1]=='B')present[2]=true;
if(!present[0])res[j]='R';
else if(!present[1])res[j]='G';
else if(!present[2])res[j]='B';
}
}
for(int i=0;i<N;i++){
if(res[i]=='$'){
if(S[i]=='R')res[i]='B';
else if(S[i]=='B')res[i]='G';
else if(S[i]=='G')res[i]='R';
}
for(int j=i+1;j<N;j++){
if(arr[j-1]!=1)break;
vector<bool> present(3);
if(S[j]=='R')present[0]=true;
else if(S[j]=='G')present[1]=true;
else if(S[j]=='B')present[2]=true;
if(res[j-1]=='R')present[0]=true;
else if(res[j-1]=='G')present[1]=true;
else if(res[j-1]=='B')present[2]=true;
if(!present[0])res[j]='R';
else if(!present[1])res[j]='G';
else if(!present[2])res[j]='B';
}
}
return res;
}
vector<int> generateDe(int n){
vector<int> debrujin;
n--;
vector<pair<bool,bool>> visited(1<<n);
function<void(int)> dfs = [&](int x){
if(!visited[x].first){
visited[x].first=true;
dfs((x<<1)&((1<<n)-1));
debrujin.emplace_back(0);
}
if(!visited[x].second){
visited[x].second=true;
dfs(((x<<1)&((1<<n)-1))+1);
debrujin.emplace_back(1);
}
};
dfs(0);
for(int i=1;i<=n;i++)debrujin.emplace_back(0);
return debrujin;
}
}
pair<string, int> anna(int N, string S) {
if(N<=61){
string res;
for(int i=0;i<N;i++){
if(S[i]=='R')res.insert(res.end(),'B');
else if(S[i]=='B')res.insert(res.end(),'G');
else if(S[i]=='G')res.insert(res.end(),'R');
}
return {res,N};
}
auto debrujin = generateDe(18);
vector<int> res(N+6,2);
int itr = 0;
for(int i=0;i<N;i+=3){
if(debrujin[itr++]==0){
res[i]=0;
res[i+1]=1;
} else {
res[i-1]=res[i]=res[i+1]=1;
}
}
return {calc(res,S),61};
}
#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int N;
int l;
vector<int> generateDe(int n){
vector<int> debrujin;
n--;
vector<pair<bool,bool>> visited(1<<n);
function<void(int)> dfs = [&](int x){
if(!visited[x].first){
visited[x].first=true;
dfs((x<<1)&((1<<n)-1));
debrujin.emplace_back(0);
}
if(!visited[x].second){
visited[x].second=true;
dfs(((x<<1)&((1<<n)-1))+1);
debrujin.emplace_back(1);
}
};
dfs(0);
for(int i=1;i<=n;i++)debrujin.emplace_back(0);
return debrujin;
}
vector<int> debrujin;
map<int,int> lookup;
} // namespace
void init(int N, int l) {
::N = N;
::l = l;
debrujin = generateDe(18);
for(int i=0;i<N;i++){
int curr = 0;
for(int j=0;j<20;j++){
if(debrujin[i+j])curr|=(1<<j);
}
lookup[curr]=i;
}
}
int bruno(string u) {
if(N<=61)return 1;
vector<int> res(l-1);
for(int i=0;i<l-1;i++)res[i]=u[i]!=u[i+1];
bool found = false;
int offset = 0;
for(int i=0;i<l-2;i++){
if(res[i])continue;
if(res[i+1]==0)offset=(i+1)%3;
else offset = i%3;
found = true;
break;
}
assert(found);
vector<int> myseq;
for(int i=offset;i<l-1;i+=3){
if(myseq.size()==20)break;
myseq.emplace_back(res[i]);
}
int curr = 0;
for(int i=0;i<20;i++){
if(myseq[i])curr|=(1<<i);
}
return lookup[curr]*3+1-offset;
assert(false);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |