Submission #995177

#	Time	Username	Problem	Language	Result	Execution time	Memory
995177		cadmiumsky	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	331 ms	3264 KiB

monochrome

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5;

#define lsb(x) (x & -x)
struct AIB {
   vector<int> tree;
   void init(int n) { tree.assign(n + 5, 0); }
   void upd(int p, int x) {
      while(p < sz(tree)) tree[p] += x, p += lsb(p);
   }
   int query(int p) {
      int sum = 0;
      while(p > 0) sum += tree[p], p -= lsb(p);
      return sum;
   }
};

int n;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // trebuia sa o incerc
ll init(string s, int a = rng() % (2 * n + 1)) {
   s = s.substr(a) + s.substr(0, a);
   stringstream haha;
   haha << s;
   
   queue<int> que[2];
   AIB aib;
   aib.init(n);
   for(int i = 1; i <= n; i++) {
      char ch;
      haha >> ch;
      if(ch == 'B') que[0].emplace(i);
      else que[1].emplace(i);
   }
   
   for(int i = 1; i <= n; i++) aib.upd(i, 1);
   ll sum = 0;
   
   for(int i = 1; i <= n; i++) {
      char ch;
      int P;
      haha >> ch;
      if(ch == 'B') P = que[1].front(), que[1].pop();
      else P = que[0].front(), que[0].pop();
      sum += aib.query(n) - aib.query(P);
      aib.upd(P, -1);
   }
   return sum;
}

signed main() {
   ld S = clock();
   cin.tie(0) -> sync_with_stdio(0);
   cin >> n;
   
   string s;
   cin >> s;
   ll rez = 0;
   for(int i = 0; i < n; i++)
      if(s[i] != s[i + n]) { rez = init(s, i); break; }
   
   ld A = clock();
   
   while(clock() - S < (ld)CLOCKS_PER_SEC * 1.85 && clock() - A < (ld) CLOCKS_PER_SEC * 0.3) // ok ultima oara promit
      rez = max(rez, init(s));
   
   cout << rez << '\n';
      
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 0 / 65