Submission #995636

#	Time	Username	Problem	Language	Result	Execution time	Memory
995636		cadmiumsky	Monochrome Points (JOI20_monochrome)	C++17	4 / 100	1 ms	604 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;
   
   int sum = 0;
   for(int i = 0; i < n; i++) {
      sum += s[i] == 'B';
   }
   
   int l = 0, r = n - 1; // m-am dat batut din a mai gandi
   while(r - l > 10) {
      int l1 = (2 * l + r) / 3, r1 = (l + 2 * r) / 3;
      if(init(s, l1) > init(s, r1)) r = r1;
      else l = l1;
   }
   for(int i = l; i <= r; i++) rez = max(rez, init(s, i));
      
   
   cout << rez << '\n';
      
}

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

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:63:7: warning: unused variable 'S' [-Wunused-variable]
   63 |    ld S = clock();
      |       ^

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