Submission #1214636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214636		edogawa_something	Tricolor Lights (JOI24_tricolor)	C++20	0 / 100	47 ms	21156 KiB

Anna

#include "Anna.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first 
#define S second 
#define pb push_back
#define all(v) v.begin(),v.end()
const ll M=6e5+10;
const ll inf=2e18;
namespace{
vii v,c,pr;
bool vis[M];
void dfs(ll x){
    if(vis[x])
    return;
    vis[x]=1;
    x/=2;
    if(vis[x]&&vis[x+(1<<17)])
    return;
    if(vis[x+(1<<17)])
    v.pb(0),dfs(x);
    else 
    v.pb(1),dfs(x+(1<<17));
}
void push(ll x){
    bool vis[3];
    vis[0]=vis[1]=vis[2]=0;
    if(c.empty()){
        vis[pr[0]]=1;
        for(int i=0;i<3;i++){
            if(!vis[i]){
                c.pb(i);
                break;
            }
        }
        vis[pr[0]]=0;
        vis[c[0]]=1,vis[pr[1]]=1;
        for(int i=0;i<3;i++){
            if(!vis[i]){
            c.pb(i);
            break;
            }
        }
        vis[0]=vis[1]=vis[2]=0;
        vis[c[1]]=1,vis[pr[2]]=1;
        for(int i=0;i<3;i++){
            if(!vis[i]){
            c.pb(i);
            break;
            }
        }
    }
    else if(x==0){
        vis[c.back()]=1;
        vis[pr[c.size()]]=1;
        for(int i=0;i<3;i++){
            if(!vis[i]){
            c.pb(i);
            break;
            }
        }
        vis[0]=vis[1]=vis[2]=0;
        vis[c.back()]=1;
        vis[pr[c.size()]]=1;
        for(int i=0;i<3;i++){
            if(!vis[i]){
            c.pb(i);
            break;
            }
        }
    }
    else{
        vis[c.back()]=1;
        vis[pr[c.size()]]=1;
        vis[pr[c.size()+1]]=1;
        if(vis[0]&&vis[1]&&vis[2])
        vis[c.back()]=0;
        for(int i=0;i<3;i++){
            if(!vis[i]){
                c.pb(i);
                c.pb(i);
                break;
            }
        }
        vis[0]=vis[1]=vis[2]=0;
        vis[c.back()]=vis[pr[c.size()]]=1;
        for(int i=0;i<3;i++){
            if(!vis[i]){
                c.pb(i);
                break;
            }
        }
    }
}
};
pair<string, int> anna(int N,string s) {
    for(auto it:s){
        if(it=='G')
        pr.pb(1);
        if(it=='R')
        pr.pb(0);   
        if(it=='B')
        pr.pb(2);
    }
    while(pr.size()<M)
    pr.pb(0);
    for(int i=0;i<18;i++)
    v.pb(0);
    dfs(0); 
    string ans;
    for(auto it:v)
    push(it);
    for(int i=0;i<N;i++){
        if(c[i]==1)
        ans.pb('G');
        if(c[i]==0)
        ans.pb('R');
        if(c[i]==2)
        ans.pb('B');
    }
    return make_pair(ans,min(N,60));
}

Bruno

#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first 
#define S second 
#define pb push_back
#define all(v) v.begin(),v.end()
const ll M=6e5+10;
const ll inf=2e18;
namespace {
bool vis[M];
vii v;
void dfs(ll x){
    if(vis[x])
    return;
    v.pb(x);
    vis[x]=1;
    x/=2;
    if(vis[x]&&vis[x+(1<<17)])
    return;
    if(vis[x+(1<<17)])
    dfs(x);
    else 
    dfs(x+(1<<17));
}
ll n,L;
};
ll ind[M];
void init(int N, int l) {
	n=N;
	L=l;
	dfs(0);
	for(int i=0;i<v.size();i++)
	ind[v[i]]=2*i+1;
}
int bruno(string u) {
	vii c;
	if(n==L)
	return 1;
	for(int i=0;i<u.size()-1;i++){
		if(u[i]==u[i+1])
		c.pb(0);
		else
		c.pb(1);
	}
	bool odd=0;
	bool cc=0;
	for(int i=0;i<c.size()-1;i++){
		if(c[i]==0&&c[i+1]==1){
			if(i%2==cc){
			odd=1;
			}
			else
			cc^=1;
		}
	}
	ll x=0;
	ll cnt=0;
	for(int i=odd;cnt<18;i+=2){
		if(c[i+1]==0){
		x+=(1<<cnt);
		cnt++;
		i++;
		}
		else
		cnt++;
	}
	x=ind[x];
  	return x-odd;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 15
• Subtask 5: 0 / 70