Language: C++

#include <iostream>
#include <cstdlib>

#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include "sys/time.h"
using namespace std;
#define HERE (cerr << "LINE: " << __LINE__ << " " << __FUNCTION__ << endl)

#define DBG(x) cerr << #x << ": " << x << endl

struct timeval timer_begin, timer_end;
uint64_t tsc_begin;
double sec_per_count = 1.0 / 2.7e9;
int timer_called;
inline uint64_t get_time_64() {
  uint32_t lo, hi;
  asm volatile ("rdtsc" : "=a" (lo), "=d" (hi));
  return (((uint64_t)hi << 32) | lo);
}

inline void timer_start() 
{
  timer_called++;
  gettimeofday(&timer_begin, NULL);
  tsc_begin = get_time_64();
}     
inline double timer_now() 
{
  if (sec_per_count < 0) {
    timer_called++;
    gettimeofday(&timer_end, NULL);         
    double duration = timer_end.tv_sec - timer_begin.tv_sec +
      (timer_end.tv_usec - timer_begin.tv_usec)/1000000.0;
    uint64_t tsc_duration = get_time_64() - tsc_begin;
    sec_per_count = duration / tsc_duration;
    DBG(1/sec_per_count);
  }
  return (get_time_64() - tsc_begin) * sec_per_count;
}
void timer_stat() {
  DBG(1/sec_per_count);
  {
    timer_called++;
    gettimeofday(&timer_end, NULL);         
    double duration = timer_end.tv_sec - timer_begin.tv_sec +
      (timer_end.tv_usec - timer_begin.tv_usec)/1000000.0;
    uint64_t tsc_duration = get_time_64() - tsc_begin;

    DBG(duration);
    DBG(tsc_duration);
    DBG(tsc_duration / duration);
  }
}

template<class T>
const T& clamp(const T& v,const T& lo,const T& hi) {
  return (v < lo) ? lo : (v > hi) ? hi : v;
}
template<typename T>
void assign_min_max(T& min,T& max,const T& x) {
  if (x < min)
    min = x;
  if (x > max)
    max = x;
}
unsigned int hash_function(unsigned long p) {
  // xor32()
  p ^= p<<7;
  p ^= p>>1;
  p ^= p<<25;
  unsigned int c = __builtin_popcount(p);
  return p<<c | p>>(32-c);
}
uint64_t hash_function64(uint64_t p) {
  // xor64()
  p ^= p<<16;
  p ^= p>>7;
  p ^= p<<39;
  uint64_t c = __builtin_popcount(p);
  return p<<c | p>>(64-c);
}  

struct xor128_t {
  uint64_t x, y, z, w;

  xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
    for (int i=0; i<48; i++)
      get();
  }

  void init(int seed) {
    x = 123456789^seed;
    y = 362436069;
    z = 521288629;
    w = 88675123;

    for (int i=0; i<48; i++)
      get();
  }

  inline uint64_t get() {
    uint64_t t=(x^(x<<11)); x=y; y=z; z=w;
    return (w=(w^(w>>19))^(t^(t>>8)));
  }

  inline uint64_t get(unsigned int sz) {
    if (sz <= 1)
      return 0;

    uint64_t x;
    const uint64_t mask = (1<<(ilogb(sz-1)+1)) - 1;
    //cout << sz << " " << mask << endl;
    assert(mask >= (sz-1) && mask < 2*sz-1);
    do {
      x = get() & mask;
    } while (x >= sz);

    return x;
  }

  inline int64_t get(int beg,int end) {
    return get(end-beg) + beg;
  }

  double get_double() {
    static const double double_factor = 1.0 / (1.0 + 0xffffffffffffffffuLL);
    return get() * double_factor;
  }

  double get_norm() {
    double a = get_double();
    double b = get_double();

    return sqrt(-2*log(a)) * cos(2*M_PI*b);
  }

  double get_gamma(double a) {
    if (a < 1.0) {
      return get_gamma(1+a) * pow(get_double(), 1/a);
    }
    
    double d = a - 1/3.0;
    double c = 1/sqrt(9.0 * d);

    while (true) {
      double x = get_norm();
      double uni = 1 - get_double();
      double v = (1.0+c*x)*(1.0+c*x)*(1.0+c*x);
      if (v > 0 && log(uni) < 0.5 * x*x + d - d*v + d*log(v))
	return d*v;
    }
  }

  template<typename T> void shuffle(vector<T>& v,int partial=-1) {
    int sz = v.size();
    if (partial < 0 || partial > sz)
      partial = sz;

    for (int i=0; i<partial; i++) {
      swap(v[i], v[i + get(sz-i)]);
    }
  }
  
  template<typename T> T sample(const vector<T>& v) {
    assert(!v.empty());
    return v[get(v.size())];
  }
};

// Van der Corput sequence
double vdc(int i,int base) {
  double result = 0;
  double f = 1;

  while (i > 0) {
    f /= base;
    result += f * (i%base);
    i = i/base;
  }

  return result;
}

struct uf_t {
  vector <int16_t> parent;

  void clear() {
    parent.clear();
  }

  void add(int elm) {
    if (elm >= parent.size()) 
      parent.resize(elm+1, -1);
  }

  void merge(int a,int b) {
    add(a);
    add(b);

    int ia = a;
    int ib = b;

    if ((ia^ib)&1) swap(ia, ib);  // ok?
      
    int ra = root(ia);
    int rb = root(ib);

    if (ra != rb) {
      parent[ra] += parent[rb];
      parent[rb] = ra;
    }
  }

  int size(int elm) {
    return -parent[root(elm)];
  }

  int id(int elm) {
    return root(elm);
  }

  int root(int ia) {
    add(ia);
    return (parent[ia] < 0) ? ia : (parent[ia] = root(parent[ia]));
  }
};

struct reusable_set_t {
  typedef uint8_t mark_t;
  mark_t mark;
  vector<mark_t> v;
  reusable_set_t() {}
  reusable_set_t(int n) : v(n), mark(1) {}

  void insert(int x) { v[x] = mark; }
  void erase(int x) { v[x] = mark-1; }
  int count(int x) const { return (v[x] == mark); }
  void clear() {
    mark++;
    if (mark == 0) {
      fill(v.begin(), v.end(), 0);
      mark ++;
    }
  }
};

struct sa_t {
  double ini, fin, inv_T, progress;
  int num_call, num_accept, num_better;
  xor128_t rng;
  sa_t() {}
  sa_t(double ini, double fin) : ini(ini), fin(fin), num_accept(0), num_call(0), num_better(0) {
    set_progress(0);
  }

  void set_progress(double x) {
    progress = clamp(x, 0.0, 1.0);
    inv_T = 1 / (ini * pow(fin/ini, progress));
  }

  bool acceptable(double x) {
    //bool result = (x > 0) || rng.get_double() < exp(x*inv_T);
    //bool result = (x > 0) || log(1-rng.get_double()) < x*inv_T;
    double z = x*inv_T;
    bool result = (x > 0) || (z > -12 && log(1-rng.get_double()) < z);

    //num_call ++;
    //num_accept += result;
    //num_better += (x > 0);

    return result;
  }

  void show_log() const {
    cerr << "better/accept/call: "
	 << num_better
	 << "/" << num_accept
	 << "/" << num_call 
	 << " " << (double)num_accept/num_call << endl;
  }
};


template <typename T>
struct pool_t {
  vector<T> v;
  int N;

  pool_t(int sz=0) : v(sz), N(0) {}

  void clear() { N = 0; }
  T& next() {
    N++;
    while (N >= v.size())
      v.resize(v.size()*11/10 + 1);
    return v[N-1];
  }

  typename vector<T>::iterator begin() { return v.begin(); }
  typename vector<T>::iterator end() { return v.begin()+N; }
  T& operator[](int i) { return v[i]; }
  size_t size() const { return N; }
  void resize(int sz) { assert(sz <= N); N = sz; }
  void swap(pool_t<T>& pl) {
    v.swap(pl.v);
    std::swap(N, pl.N);
  }
};

template <typename Score_t,typename Item_t,typename HashFunc_t>
struct best_k_t {
  vector<pair<Score_t,int>> v;
  vector<Item_t> items;
  HashFunc_t hashfunc;
  set<uint32_t> used;
  bool never_push;

  best_k_t() : never_push(false) {}

  void push_force(const Score_t sc,const Item_t& e) {
    int id = items.size();
    items.push_back(e);

    int n = v.size();
    v.push_back(pair<Score_t,int>(sc,id));

    int m = (n+1)/2 - 1;
    while (n > 0 && v[n] < v[m]) {
      swap(v[n], v[m]);
      n = m;
      m = (n+1)/2 - 1;
    }
  }

  bool push(const Score_t sc,const Item_t& e,int w) {
    assert(!never_push);
    if (v.size() < w) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	used.insert(h);
	push_force(sc, e);
	return true;
      } else {
	return false;
      }
    } else if (sc > v[0].first) {
      auto h = hashfunc(e);
      if (!used.count(h)) {
	int id = v[0].second;
	v[0].first = sc;
	items[id] = e;
	used.insert(h);
	rebuild();
	return true;
      } else {
	return false;
      }
    }
    return false;
  }

  bool match(const Score_t sc,int w) {
    return (v.size() < w || sc > v[0].first);
  }

  void rebuild() {
    int n = 0;
    while (true) {
      int L = (n+1)*2 - 1;
      int R = L+1;

      if (L >= v.size()) 
	break;

      int m = (R >= v.size() || v[L] < v[R]) ? L : R;

      if (v[m] < v[n]) {
	swap(v[m], v[n]);
	n = m;
      } else {
	break;
      }
    }
  }

  Item_t pop() {
    // fix me
    never_push = true;
    
    int id = v[0].second;
    Item_t ret = items[id];

    v[0] = v.back();
    v.pop_back();

    rebuild();

    return ret;
  }
  Item_t top() { return v[0].second; }

  Item_t best() const {
    int best_i = 0;
    for (int i=0; i<v.size(); i++) {
      if (v[i] < v[best_i])
	best_i = i;
    }
    return items[v[best_i].second];
  }

  void clear() { v.clear(); }
  bool empty() const { return v.empty(); }
  int size() const { return v.size(); }
};

template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[ ";
  for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " ]"; 
  return os; 
}
template<typename T> ostream& operator<<(ostream& os, const set<T>& v) {
  os << "{ ";
  for(typename set<T>::const_iterator it=v.begin(); it!=v.end(); ++it) {
    if (it != v.begin())
      os << ", ";
    os << *it; 
  }
  os << " }"; 
  return os; 
}
template<typename T1,typename T2> ostream& operator<<(ostream& os, const pair<T1,T2>& v) {
  os << "[ " << v.first << ", " << v.second << "]";
  return os; 
}

#ifdef LOCAL
double TIME_LIMIT_FACTOR = 0.55;
#else
double TIME_LIMIT_FACTOR = 1.0;
#endif
double TIME_LIMIT = TIME_LIMIT_FACTOR * 10.0;

/* insert here */
int64_t solve(int N,const string& S) {
  vector<int> cnt(N*9);
  
  for (int i=0; i<N; i++)
    for (int j=i+1; j<N; j++) {
      if (S[i] == S[j])
        continue;
      int type = (S[i]%3)*3+(S[j]%3);
      cnt[i*9+type] ++;
    }

  int64_t sum = 0;
  for (int i=0; i<N; i++)
    for (int j=i+1; j<N; j++) {
      if (S[i] == S[j])
        continue;
      int type_k = (3 - (S[i]%3+S[j]%3));
      int type = (S[j]%3)*3 + type_k;
      sum += cnt[j*9+type];

      if (2*j-i < N) {
        int k = 2*j-i;
        sum -= (S[k]%3 == type_k);
      }
    }

  return sum;
}


int main() {
  int N;
  string S;
  cin >> N; cin.ignore();
  cin >> S;

  auto ret = solve(N, S);
  cout << ret << endl;

  return 0;
}
  


Compiler output:
a.cc:25:1: error: 'uint64_t' does not name a type
   25 | uint64_t tsc_begin;
      | ^~~~~~~~
a.cc:19:1: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
   18 | #include "sys/time.h"
  +++ |+#include <cstdint>
   19 | using namespace std;
a.cc:28:8: error: 'uint64_t' does not name a type
   28 | inline uint64_t get_time_64() {
      |        ^~~~~~~~
a.cc:28:8: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc: In function 'void timer_start()':
a.cc:38:3: error: 'tsc_begin' was not declared in this scope; did you mean 'timer_begin'?
   38 |   tsc_begin = get_time_64();
      |   ^~~~~~~~~
      |   timer_begin
a.cc:38:15: error: 'get_time_64' was not declared in this scope; did you mean 'getitimer'?
   38 |   tsc_begin = get_time_64();
      |               ^~~~~~~~~~~
      |               getitimer
a.cc: In function 'double timer_now()':
a.cc:47:5: error: 'uint64_t' was not declared in this scope
   47 |     uint64_t tsc_duration = get_time_64() - tsc_begin;
      |     ^~~~~~~~
a.cc:47:5: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:48:32: error: 'tsc_duration' was not declared in this scope; did you mean 'duration'?
   48 |     sec_per_count = duration / tsc_duration;
      |                                ^~~~~~~~~~~~
      |                                duration
a.cc:51:11: error: 'get_time_64' was not declared in this scope; did you mean 'getitimer'?
   51 |   return (get_time_64() - tsc_begin) * sec_per_count;
      |           ^~~~~~~~~~~
      |           getitimer
a.cc:51:27: error: 'tsc_begin' was not declared in this scope; did you mean 'timer_begin'?
   51 |   return (get_time_64() - tsc_begin) * sec_per_count;
      |                           ^~~~~~~~~
      |                           timer_begin
a.cc: In function 'void timer_stat()':
a.cc:60:5: error: 'uint64_t' was not declared in this scope
   60 |     uint64_t tsc_duration = get_time_64() - tsc_begin;
      |     ^~~~~~~~
a.cc:60:5: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:63:9: error: 'tsc_duration' was not declared in this scope; did you mean 'duration'?
   63 |     DBG(tsc_duration);
      |         ^~~~~~~~~~~~
a.cc:22:38: note: in definition of macro 'DBG'
   22 | #define DBG(x) cerr << #x << ": " << x << endl
      |                                      ^
a.cc: At global scope:
a.cc:87:1: error: 'uint64_t' does not name a type
   87 | uint64_t hash_function64(uint64_t p) {
      | ^~~~~~~~
a.cc:87:1: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:97:3: error: 'uint64_t' does not name a type
   97 |   uint64_t x, y, z, w;
      |   ^~~~~~~~
a.cc:97:3: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:114:10: error: 'uint64_t' does not name a type
  114 |   inline uint64_t get() {
      |          ^~~~~~~~
a.cc:114:10: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:119:10: error: 'uint64_t' does not name a type
  119 |   inline uint64_t get(unsigned int sz) {
      |          ^~~~~~~~
a.cc:119:10: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc: In constructor 'xor128_t::xor128_t(int)':
a.cc:99:26: error: class 'xor128_t' does not have any field named 'x'
   99 |   xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
      |                          ^
a.cc:99:46: error: class 'xor128_t' does not have any field named 'y'
   99 |   xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
      |                                              ^
a.cc:99:60: error: class 'xor128_t' does not have any field named 'z'
   99 |   xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
      |                                                            ^
a.cc:99:74: error: class 'xor128_t' does not have any field named 'w'
   99 |   xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
      |                                                                          ^
a.cc:101:10: error: no matching function for call to 'xor128_t::get()'
  101 |       get();
      |       ~~~^~
a.cc:134:18: note: candidate: 'int64_t xor128_t::get(int, int)'
  134 |   inline int64_t get(int beg,int end) {
      |                  ^~~
a.cc:134:18: note:   candidate expects 2 arguments, 0 provided
a.cc: In member function 'void xor128_t::init(int)':
a.cc:105:5: error: 'x' was not declared in this scope
  105 |     x = 123456789^seed;
      |     ^
a.cc:106:5: error: 'y' was not declared in this scope; did you mean 'yn'?
  106 |     y = 362436069;
      |     ^
      |     yn
a.cc:107:5: error: 'z' was not declared in this scope
  107 |     z = 521288629;
      |     ^
a.cc:108:5: error: 'w' was not declared in this scope
  108 |     w = 88675123;
      |     ^
a.cc:111:10: error: no matching function for call to 'xor128_t::get()'
  111 |       get();
      |       ~~~^~
a.cc:134:18: note: candidate: 'int64_t xor128_t::get(int, int)'
  134 |   inline int64_t get(int beg,int end) {
      |                  ^~~
a.cc:134:18: note:   candidate expects 2 arguments, 0 provided
a.cc: In member function 'int64_t xor128_t::get(int, int)':
a.cc:135:15: error: no matching function for call to 'xor128_t::get(int)'
  135 |     return get(end-beg) + beg;
      |            ~~~^~~~~~~~~
a.cc:134:18: note: candidate: 'int64_t xor128_t::get(int, int)'
  134 |   inline int64_t get(int beg,int end) {
      |                  ^~~
a.cc:134:18: note:   candidate expects 2 arguments, 1 provided
a.cc: In member function 'double xor128_t::get_double()':
a.cc:140:15: error: no matching function for call to 'xor128_t::get()'
  140 |     return get() * double_factor;
      |            ~~~^~
a.cc:134:18: note: candidate: 'int64_t xor128_t::get(int, int)'
  134 |   inline int64_t get(int beg,int end) {
      |                  ^~~
a.cc:134:18: note:   candidate expects 2 arguments, 0 provided
a.cc: In member function 'void xor128_t::shuffle(std::vector<_Tp>&, int)':
a.cc:173:27: error: no matching function for call to 'xor128_t::get(int)'
  173 |       swap(v[i], v[i + get(sz-i)]);
      |                        ~~~^~~~~~
a.cc:134:18: note: candidate: 'int64_t xor128_t::get(int, int)'
  134 |   inline int64_t get(int beg,int end) {
      |                  ^~~
a.cc:134:18: note:   candidate expects 2 arguments, 1 provided
a.cc: At global scope:
a.cc:242:11: error: 'uint8_t' does not name a type
  242 |   typedef uint8_t mark_t;
      |           ^~~~~~~
a.cc:242:11: note: 'uint8_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:243:3: error: 'mark_t' does not name a type
  243 |   mark_t mark;
      |   ^~~~~~
a.cc:244:10: error: 'mark_t' was not declared in this scope
  244 |   vector<mark_t> v;
      |          ^~~~~~
a.cc:244:16: error: template argument 1 is invalid
  244 |   vector<mark_t> v;
      |                ^
a.cc:244:16: error: template argument 2 is invalid
a.cc: In constructor 'reusable_set_t::reusable_set_t(int)':
a.cc:246:33: error: class 'reusable_set_t' does not have any field named 'mark'
  246 |   reusable_set_t(int n) : v(n), mark(1) {}
      |                                 ^~~~
a.cc: In member function 'void reusable_set_t::insert(int)':
a.cc:248:25: error: invalid types 'int[int]' for array subscript
  248 |   void insert(int x) { v[x] = mark; }
      |                         ^
a.cc:248:31: error: 'mark' was not declared in this scope
  248 |   void insert(int x) { v[x] = mark; }
      |                               ^~~~
a.cc: In member function 'void reusable_set_t::erase(int)':
a.cc:249:24: error: invalid types 'int[int]' for array subscript
  249 |   void erase(int x) { v[x] = mark-1; }
      |                        ^
a.cc:249:30: error: 'mark' was not declared in this scope
  249 |   void erase(int x) { v[x] = mark-1; }
      |                              ^~~~
a.cc: In member function 'int reusable_set_t::count(int) const':
a.cc:250:37: error: invalid types 'const int[int]' for array subscript
  250 |   int count(int x) const { return (v[x] == mark); }
      |                                     ^
a.cc:250:44: error: 'mark' was not declared in this scope
  250 |   int count(int x) const { return (v[x] == mark); }
      |                                            ^~~~
a.cc: In member function 'void reusable_set_t::clear()':
a.cc:252:5: error: 'mark' was not declared in this scope
  252 |     mark++;
      |     ^~~~
a.cc:254:14: error: request for member 'begin' in '((reusable_set_t*)this)->reusable_set_t::v', which is of non-class type 'int'
  254 |       fill(v.begin(), v.end(), 0);
      |              ^~~~~
a.cc:254:25: error: request for member 'end' in '((reusable_set_t*)this)->reusable_set_t::v', which is of non-class type 'int'
  254 |       fill(v.begin(), v.end(), 0);
      |                         ^~~
a.cc: In member function 'void sa_t::set_progress(double)':
a.cc:270:21: error: call of overloaded 'clamp(double&, double, double)' is ambiguous
  270 |     progress = clamp(x, 0.0, 1.0);
      |                ~~~~~^~~~~~~~~~~~~
a.cc:69:10: note: candidate: 'const T& clamp(const T&, const T&, const T&) [with T = double]'
   69 | const T& clamp(const T& v,const T& lo,const T& hi) {
      |          ^~~~~
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:13:
/usr/include/c++/14/bits/stl_algo.h:3624:5: note: candidate: 'constexpr const _Tp& std::clamp(const _Tp&, const _Tp&, const _Tp&) [with _Tp = double]'
 3624 |     clamp(const _Tp& __val, const _Tp& __lo, const _Tp& __hi)
      |     ^~~~~
a.cc: At global scope:
a.cc:328:7: error: 'uint32_t' was not declared in this scope
  328 |   set<uint32_t> used;
      |       ^~~~~~~~
a.cc:328:7: note: 'uint32_t' is defined in header '<cstdint>'