oj.uz

Submission #296307

# Submission time Handle Problem Language Result Execution time Memory
296307 2020-09-10T13:23:35 Z Mlxa Monochrome Points (JOI20_monochrome) C++14
4 / 100
 2000 ms 8320 KB 
#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif
using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second

const int INPUT_BUF = 1 << 12;
const int OUTPUT_BUF = 1 << 16;
char input[INPUT_BUF];
char output[OUTPUT_BUF];
int input_ptr = 0;
int input_len = 0;
int output_ptr = 0;

inline
bool check_eof() {
    if (input_ptr == input_len) {
        input_ptr = 0;
        input_len = fread(input, 1, INPUT_BUF, stdin);
    }
    return input_ptr == input_len;
}
inline
char get_char() {
    assert(!check_eof());
    return input[input_ptr++];
}
inline
char read_char() {
    char c = get_char();
    while (c <= ' ') {
        c = get_char();
    }
    return c;
}
inline
int read_int() {
    int sgn = +1;
    char c = read_char();
    if (c == '-') {
        sgn = -1;
        c = get_char();
    }
    int x = 0;
    while ('0' <= c && c <= '9') {
        x = 10 * x + c - '0';
        c = get_char();
    }
    return x * sgn;

}
inline
__attribute__((destructor))
void flush_output() {
    fwrite(output, 1, output_ptr, stdout);
    output_ptr = 0;
}
inline
void write(char c) {
    if (output_ptr == OUTPUT_BUF) {
        flush_output();
    }
    output[output_ptr++] = c;
}
inline
void write(signed x) {
    static const int LEN = 20;
    static char tmp[LEN];
    int n = 0;
    if (x < 0) {
        write('-');
        x *= -1;
    }
    while (!n || x) {
        tmp[n++] = (char)(x % 10 + '0');
        x /= 10;
    }
    while (n--) {
        write(tmp[n]);
    }
}
inline
void write(long long x) {
    static const int LEN = 20;
    static char tmp[LEN];
    int n = 0;
    if (x < 0) {
        write('-');
        x *= -1;
    }
    while (!n || x) {
        tmp[n++] = (char)(x % 10 + '0');
        x /= 10;
    }
    while (n--) {
        write(tmp[n]);
    }
}
inline
void write(string s) {
    for (char c : s) {
        write(c);
    }
}
inline
void write(const char *s) {
    for (const char *ptr = s; *ptr; ++ptr) {
        write(*ptr);
    }
}

const int N = 1e6;
int n;
char s[N];
vector<int> g[2];
int fen[N];
void clear() {
    fill_n(fen, N, 0);
}
void add(int i) {
    for (; i < N; i |= i + 1) {
        ++fen[i];
    }
}
int sum(int i) {
    int s = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) {
        s += fen[i];
    }
    return s;
}
int go[N];
int func(int k) {
    int s = 0;
    for (int i = 0; i < (int)g[0].size(); ++i) {
        int j = (i + k) % (int)g[1].size();
        go[g[0][i]] = g[1][j];
        go[g[1][j]] = g[0][i];
    }
    clear();
    for (int i = n - 1; i >= 0; --i) {
        if (go[i] <= i) {
            s += sum(i) - sum(go[i]);
            add(go[i]);
        }
    }
    clear();
    for (int i = 0; i < n; ++i) {
        if (i <= go[i]) {
            s += sum(go[i]) - sum(i);
            add(go[i]);
        }
    }
    return s / 2;
}

int32_t main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
    //assert(freopen("output.txt", "w", stdout));
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    
    n = read_int();
    n *= 2;
    for (int i = 0; i < n; ++i) {
        if ((s[i] = read_char()) == 'W') {
            g[0].push_back(i);
        } else {
            g[1].push_back(i);
        }
    }
    int ans = 0;
    for (int i = 0; i < 2 * n; ++i) {
        ans = max(ans, func(i));
    }
    write(ans);
    write('\n');
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8192 KB Output is correct
2 Correct 20 ms 8192 KB Output is correct
3 Correct 30 ms 8320 KB Output is correct
4 Correct 35 ms 8232 KB Output is correct
5 Correct 47 ms 8192 KB Output is correct
6 Correct 52 ms 8224 KB Output is correct
7 Correct 59 ms 8192 KB Output is correct
8 Correct 60 ms 8192 KB Output is correct
9 Correct 66 ms 8192 KB Output is correct
10 Correct 68 ms 8240 KB Output is correct
11 Correct 65 ms 8312 KB Output is correct
12 Correct 66 ms 8192 KB Output is correct
13 Correct 65 ms 8192 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8192 KB Output is correct
2 Correct 20 ms 8192 KB Output is correct
3 Correct 30 ms 8320 KB Output is correct
4 Correct 35 ms 8232 KB Output is correct
5 Correct 47 ms 8192 KB Output is correct
6 Correct 52 ms 8224 KB Output is correct
7 Correct 59 ms 8192 KB Output is correct
8 Correct 60 ms 8192 KB Output is correct
9 Correct 66 ms 8192 KB Output is correct
10 Correct 68 ms 8240 KB Output is correct
11 Correct 65 ms 8312 KB Output is correct
12 Correct 66 ms 8192 KB Output is correct
13 Correct 65 ms 8192 KB Output is correct
14 Execution timed out 2088 ms 8192 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8192 KB Output is correct
2 Correct 20 ms 8192 KB Output is correct
3 Correct 30 ms 8320 KB Output is correct
4 Correct 35 ms 8232 KB Output is correct
5 Correct 47 ms 8192 KB Output is correct
6 Correct 52 ms 8224 KB Output is correct
7 Correct 59 ms 8192 KB Output is correct
8 Correct 60 ms 8192 KB Output is correct
9 Correct 66 ms 8192 KB Output is correct
10 Correct 68 ms 8240 KB Output is correct
11 Correct 65 ms 8312 KB Output is correct
12 Correct 66 ms 8192 KB Output is correct
13 Correct 65 ms 8192 KB Output is correct
14 Execution timed out 2088 ms 8192 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8192 KB Output is correct
2 Correct 20 ms 8192 KB Output is correct
3 Correct 30 ms 8320 KB Output is correct
4 Correct 35 ms 8232 KB Output is correct
5 Correct 47 ms 8192 KB Output is correct
6 Correct 52 ms 8224 KB Output is correct
7 Correct 59 ms 8192 KB Output is correct
8 Correct 60 ms 8192 KB Output is correct
9 Correct 66 ms 8192 KB Output is correct
10 Correct 68 ms 8240 KB Output is correct
11 Correct 65 ms 8312 KB Output is correct
12 Correct 66 ms 8192 KB Output is correct
13 Correct 65 ms 8192 KB Output is correct
14 Execution timed out 2088 ms 8192 KB Time limit exceeded
15 Halted 0 ms 0 KB -