Submission #1131444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131444		huutuan	Tricolor Lights (JOI24_tricolor)	C++20	30 / 100	244 ms	28428 KiB

Anna

#include "Anna.h"

#include <bits/stdc++.h>

using namespace std;

namespace Anna{
   mt19937 rng(69420);
   const int LEN=19;
   int n;
   string s;
   vector<string> v[3]{
      {"BB", "GG", "RR"},
      {"BG", "GR", "RB"},
      {"BR", "RG", "GB"},
   };
   pair<string, int> solve(int _n, string _s){
      n=_n, s=_s;
      if (n<LEN*2+1){
         string ans;
         for (int i=0; i<n; ++i) if (s[i]=='B') ans.push_back('G'); else ans.push_back('B');
         return {ans, n};
      }
      string s2;
      while ((int)s2.size()<n/2){
         s2.push_back(rng()%3+'0');
      }
      string ans;
      for (int i=0; i<n/2; ++i){
         int id=s2[i]-'0';
         for (auto &t:v[id]){
            if (t[0]!=s[i<<1] && t[1]!=s[i<<1|1]){
               ans+=t;
               break;
            }
         }
      }
      if ((int)ans.size()!=n){
         if (s.back()=='B') ans.push_back('G');
         else ans.push_back('B');
      }
      return {ans, LEN*2+1};
   }
}

pair<string, int> anna(int N, string S) {
   return Anna::solve(N, S);
}

Bruno

#include "Bruno.h"

#include <bits/stdc++.h>

using namespace std;

namespace Bruno{
   mt19937 rng(69420);
   const int LEN=19;
   bool small;
   map<string, int> mp;
   int n;
   vector<string> v[3]{
      {"BB", "GG", "RR"},
      {"BG", "GR", "RB"},
      {"BR", "RG", "GB"},
   };
   void init(int _n){
      n=_n;
      string s2;
      while ((int)s2.size()<n/2){
         s2.push_back(rng()%3+'0');
      }
      for (int i=0; i+LEN<=(int)s2.size(); ++i){
         mp[s2.substr(i, LEN)]=i<<1|1;
      }
   }
   int solve(string s){
      string s1, s2;
      for (int i=0; i<LEN*2; i+=2){
         for (int j=0; j<3; ++j) for (auto &k:v[j]) if (k[0]==s[i] && k[1]==s[i+1]){
            s1.push_back(j+'0');
         }
      }
      for (int i=1; i<LEN*2+1; i+=2){
         for (int j=0; j<3; ++j) for (auto &k:v[j]) if (k[0]==s[i] && k[1]==s[i+1]){
            s2.push_back(j+'0');
         }
      }
      if (mp.count(s1)) return mp[s1];
      return mp[s2]-1;
   }
}

void init(int N, int l) {
   if (N==l) Bruno::small=1;
   else Bruno::init(N);
}

int bruno(string u) {
   if (Bruno::small) return 1;
   return Bruno::solve(u);
}

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