oj.uz

Submission #995180

# Submission time Handle Problem Language Result Execution time Memory
995180 2024-06-08T15:01:26 Z cadmiumsky Monochrome Points (JOI20_monochrome) C++17
0 / 100
 1 ms 348 KB 
#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
*/

Compilation message

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

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 344 KB Output isn't correct
10 Halted 0 ms 0 KB -