oj.uz

Submission #1038747

# Submission time Handle Problem Language Result Execution time Memory
1038747 2024-07-30T07:12:34 Z phong Monochrome Points (JOI20_monochrome) C++17
35 / 100
 24 ms 11608 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>

#define ll long long
const int nmax = 2e5 + 5, N = 1e5;
const ll oo = 1e9;
const int lg = 19, M = 2, mod = 1e6;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
#define endl "\n"
#define task "code"
using namespace std;

int n;
string s;
vector<int> one, two;
vector<pii> tmp;
struct holder{
    vector<int> tmp;
    int f[nmax];

    void update(int x, int val){
        for(; x <= 2 *n; x += x&-x) f[x] += val, tmp.push_back(x);
    }
    int get(int x){
        int res = 0;
        for(; x ; x -= x&-x) res += f[x];
        return res;
    }
    void clear(){
        for(auto p : tmp) f[p] = 0;
        tmp.clear();
    }
}F, G;
ll get(int x){
    tmp.clear();
    for(int i = 0; i < n; ++i){
        int u = one[i];
        int v = two[(i + x + n * 10) % n];
        if(u > v) swap(u, v);
        tmp.push_back({u, v});
//        cout << u << ' ' << v << endl;
    }
    sort(tmp.begin(), tmp.end());
//    for(auto [u, v] : tmp) cout << u << ' ' << v << endl;
    ll ans = 0;
    for(int i = tmp.size() - 1; i >= 0; --i){
        ans += G.get(tmp[i].se) - F.get(tmp[i].se);
        F.update(tmp[i].se, 1);
        G.update(tmp[i].fi, 1);
    }
    F.clear();G.clear();
    return ans;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen(task".inp", "r", stdin);
//    freopen(task".out", "w", stdout);
    cin >> n;
    cin >> s;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == 'W') one.push_back(i + 1);
        else two.push_back(i + 1);
    }
//    cout << get(0);
//    for(int i = 0; i < n; ++i) cout << get(i) << ' ';
    int l = 0, r = n - 2, kq = -1;
    while(l <= r){
        int mid = r + l >> 1;
        if(get(mid) <= get(mid + 1)){
            kq = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    ll ans = 0;
    for(int i = kq - 10; i <= kq + 10; ++i) ans = max(ans, get(i));
    cout << ans;

}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5

4
2 1 5 3
1
1 4


*/

Compilation message

monochrome.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   59 | main(){
      | ^~~~
monochrome.cpp: In function 'int main()':
monochrome.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 0; i < s.size(); ++i){
      |                    ~~^~~~~~~~~~
monochrome.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         int mid = r + l >> 1;
      |                   ~~^~~

Subtask #1
4.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 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 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 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #2
21.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 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 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 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 524 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 472 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct

Subtask #3
10.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 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 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 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 524 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 472 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 7 ms 604 KB Output is correct
35 Correct 7 ms 776 KB Output is correct
36 Correct 7 ms 604 KB Output is correct
37 Correct 7 ms 760 KB Output is correct
38 Correct 7 ms 604 KB Output is correct
39 Correct 6 ms 604 KB Output is correct
40 Correct 5 ms 604 KB Output is correct
41 Correct 5 ms 604 KB Output is correct
42 Correct 7 ms 780 KB Output is correct
43 Correct 7 ms 728 KB Output is correct
44 Correct 7 ms 604 KB Output is correct
45 Correct 7 ms 604 KB Output is correct
46 Correct 7 ms 604 KB Output is correct
47 Correct 8 ms 728 KB Output is correct
48 Correct 6 ms 604 KB Output is correct
49 Correct 5 ms 604 KB Output is correct
50 Correct 8 ms 604 KB Output is correct
51 Correct 4 ms 604 KB Output is correct
52 Correct 9 ms 604 KB Output is correct

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 0 ms 348 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 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 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 524 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 464 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 472 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 7 ms 604 KB Output is correct
35 Correct 7 ms 776 KB Output is correct
36 Correct 7 ms 604 KB Output is correct
37 Correct 7 ms 760 KB Output is correct
38 Correct 7 ms 604 KB Output is correct
39 Correct 6 ms 604 KB Output is correct
40 Correct 5 ms 604 KB Output is correct
41 Correct 5 ms 604 KB Output is correct
42 Correct 7 ms 780 KB Output is correct
43 Correct 7 ms 728 KB Output is correct
44 Correct 7 ms 604 KB Output is correct
45 Correct 7 ms 604 KB Output is correct
46 Correct 7 ms 604 KB Output is correct
47 Correct 8 ms 728 KB Output is correct
48 Correct 6 ms 604 KB Output is correct
49 Correct 5 ms 604 KB Output is correct
50 Correct 8 ms 604 KB Output is correct
51 Correct 4 ms 604 KB Output is correct
52 Correct 9 ms 604 KB Output is correct
53 Runtime error 24 ms 11608 KB Execution killed with signal 11
54 Halted 0 ms 0 KB -