답안 #995177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995177	2024-06-08T14:59:59 Z	cadmiumsky	Monochrome Points (JOI20_monochrome)	C++17	35 / 100	331 ms	3264 KB

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.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	348 KB	Output is correct
2	Correct	301 ms	344 KB	Output is correct
3	Correct	301 ms	348 KB	Output is correct
4	Correct	300 ms	432 KB	Output is correct
5	Correct	300 ms	348 KB	Output is correct
6	Correct	300 ms	348 KB	Output is correct
7	Correct	300 ms	432 KB	Output is correct
8	Correct	301 ms	348 KB	Output is correct
9	Correct	300 ms	348 KB	Output is correct
10	Correct	300 ms	436 KB	Output is correct
11	Correct	300 ms	348 KB	Output is correct
12	Correct	300 ms	428 KB	Output is correct
13	Correct	301 ms	600 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	348 KB	Output is correct
2	Correct	301 ms	344 KB	Output is correct
3	Correct	301 ms	348 KB	Output is correct
4	Correct	300 ms	432 KB	Output is correct
5	Correct	300 ms	348 KB	Output is correct
6	Correct	300 ms	348 KB	Output is correct
7	Correct	300 ms	432 KB	Output is correct
8	Correct	301 ms	348 KB	Output is correct
9	Correct	300 ms	348 KB	Output is correct
10	Correct	300 ms	436 KB	Output is correct
11	Correct	300 ms	348 KB	Output is correct
12	Correct	300 ms	428 KB	Output is correct
13	Correct	301 ms	600 KB	Output is correct
14	Correct	301 ms	348 KB	Output is correct
15	Correct	300 ms	348 KB	Output is correct
16	Correct	301 ms	348 KB	Output is correct
17	Correct	301 ms	344 KB	Output is correct
18	Correct	300 ms	348 KB	Output is correct
19	Correct	300 ms	344 KB	Output is correct
20	Correct	301 ms	344 KB	Output is correct
21	Correct	300 ms	348 KB	Output is correct
22	Correct	301 ms	344 KB	Output is correct
23	Correct	300 ms	344 KB	Output is correct
24	Correct	300 ms	596 KB	Output is correct
25	Correct	300 ms	348 KB	Output is correct
26	Correct	300 ms	348 KB	Output is correct
27	Correct	301 ms	592 KB	Output is correct
28	Correct	301 ms	348 KB	Output is correct
29	Correct	301 ms	348 KB	Output is correct
30	Correct	301 ms	472 KB	Output is correct
31	Correct	300 ms	344 KB	Output is correct
32	Correct	301 ms	472 KB	Output is correct
33	Correct	301 ms	348 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	348 KB	Output is correct
2	Correct	301 ms	344 KB	Output is correct
3	Correct	301 ms	348 KB	Output is correct
4	Correct	300 ms	432 KB	Output is correct
5	Correct	300 ms	348 KB	Output is correct
6	Correct	300 ms	348 KB	Output is correct
7	Correct	300 ms	432 KB	Output is correct
8	Correct	301 ms	348 KB	Output is correct
9	Correct	300 ms	348 KB	Output is correct
10	Correct	300 ms	436 KB	Output is correct
11	Correct	300 ms	348 KB	Output is correct
12	Correct	300 ms	428 KB	Output is correct
13	Correct	301 ms	600 KB	Output is correct
14	Correct	301 ms	348 KB	Output is correct
15	Correct	300 ms	348 KB	Output is correct
16	Correct	301 ms	348 KB	Output is correct
17	Correct	301 ms	344 KB	Output is correct
18	Correct	300 ms	348 KB	Output is correct
19	Correct	300 ms	344 KB	Output is correct
20	Correct	301 ms	344 KB	Output is correct
21	Correct	300 ms	348 KB	Output is correct
22	Correct	301 ms	344 KB	Output is correct
23	Correct	300 ms	344 KB	Output is correct
24	Correct	300 ms	596 KB	Output is correct
25	Correct	300 ms	348 KB	Output is correct
26	Correct	300 ms	348 KB	Output is correct
27	Correct	301 ms	592 KB	Output is correct
28	Correct	301 ms	348 KB	Output is correct
29	Correct	301 ms	348 KB	Output is correct
30	Correct	301 ms	472 KB	Output is correct
31	Correct	300 ms	344 KB	Output is correct
32	Correct	301 ms	472 KB	Output is correct
33	Correct	301 ms	348 KB	Output is correct
34	Correct	301 ms	600 KB	Output is correct
35	Correct	301 ms	592 KB	Output is correct
36	Correct	301 ms	512 KB	Output is correct
37	Correct	301 ms	344 KB	Output is correct
38	Correct	300 ms	348 KB	Output is correct
39	Correct	301 ms	348 KB	Output is correct
40	Correct	301 ms	348 KB	Output is correct
41	Correct	301 ms	348 KB	Output is correct
42	Correct	301 ms	504 KB	Output is correct
43	Correct	301 ms	508 KB	Output is correct
44	Correct	301 ms	348 KB	Output is correct
45	Correct	301 ms	344 KB	Output is correct
46	Correct	301 ms	344 KB	Output is correct
47	Correct	301 ms	344 KB	Output is correct
48	Correct	301 ms	348 KB	Output is correct
49	Correct	301 ms	512 KB	Output is correct
50	Correct	301 ms	348 KB	Output is correct
51	Correct	301 ms	508 KB	Output is correct
52	Correct	300 ms	344 KB	Output is correct

Subtask #4
0.0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	300 ms	348 KB	Output is correct
2	Correct	301 ms	344 KB	Output is correct
3	Correct	301 ms	348 KB	Output is correct
4	Correct	300 ms	432 KB	Output is correct
5	Correct	300 ms	348 KB	Output is correct
6	Correct	300 ms	348 KB	Output is correct
7	Correct	300 ms	432 KB	Output is correct
8	Correct	301 ms	348 KB	Output is correct
9	Correct	300 ms	348 KB	Output is correct
10	Correct	300 ms	436 KB	Output is correct
11	Correct	300 ms	348 KB	Output is correct
12	Correct	300 ms	428 KB	Output is correct
13	Correct	301 ms	600 KB	Output is correct
14	Correct	301 ms	348 KB	Output is correct
15	Correct	300 ms	348 KB	Output is correct
16	Correct	301 ms	348 KB	Output is correct
17	Correct	301 ms	344 KB	Output is correct
18	Correct	300 ms	348 KB	Output is correct
19	Correct	300 ms	344 KB	Output is correct
20	Correct	301 ms	344 KB	Output is correct
21	Correct	300 ms	348 KB	Output is correct
22	Correct	301 ms	344 KB	Output is correct
23	Correct	300 ms	344 KB	Output is correct
24	Correct	300 ms	596 KB	Output is correct
25	Correct	300 ms	348 KB	Output is correct
26	Correct	300 ms	348 KB	Output is correct
27	Correct	301 ms	592 KB	Output is correct
28	Correct	301 ms	348 KB	Output is correct
29	Correct	301 ms	348 KB	Output is correct
30	Correct	301 ms	472 KB	Output is correct
31	Correct	300 ms	344 KB	Output is correct
32	Correct	301 ms	472 KB	Output is correct
33	Correct	301 ms	348 KB	Output is correct
34	Correct	301 ms	600 KB	Output is correct
35	Correct	301 ms	592 KB	Output is correct
36	Correct	301 ms	512 KB	Output is correct
37	Correct	301 ms	344 KB	Output is correct
38	Correct	300 ms	348 KB	Output is correct
39	Correct	301 ms	348 KB	Output is correct
40	Correct	301 ms	348 KB	Output is correct
41	Correct	301 ms	348 KB	Output is correct
42	Correct	301 ms	504 KB	Output is correct
43	Correct	301 ms	508 KB	Output is correct
44	Correct	301 ms	348 KB	Output is correct
45	Correct	301 ms	344 KB	Output is correct
46	Correct	301 ms	344 KB	Output is correct
47	Correct	301 ms	344 KB	Output is correct
48	Correct	301 ms	348 KB	Output is correct
49	Correct	301 ms	512 KB	Output is correct
50	Correct	301 ms	348 KB	Output is correct
51	Correct	301 ms	508 KB	Output is correct
52	Correct	300 ms	344 KB	Output is correct
53	Incorrect	331 ms	3264 KB	Output isn't correct
54	Halted	0 ms	0 KB	-

답안 #995177

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 21.0 / 21.0

Subtask #3 10.0 / 10.0

Subtask #4 0.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
21.0 / 21.0

Subtask #3
10.0 / 10.0

Subtask #4
0.0 / 65.0