oj.uz

Submission #1004784

# Submission time Handle Problem Language Result Execution time Memory
1004784 2024-06-21T15:07:04 Z Nailuj_217 Monochrome Points (JOI20_monochrome) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
#define l long long
using namespace std;

const l LEN = 2005;
l n;
string s;

vector<pair<l, l>> connections;
array<l, LEN> connex;

bool is_in_range(l a, l b, l k) {
    if (b >= a) {
        return (a <= k && k <= b); 
    } else {
        return (a <= k || b >= k);
    }
}


l intersections(l k) {
    if (k >= n) return 0;

    connections.clear();

    l whitecounter = 0;
    for (int i = 0; i <= k;) {
        whitecounter++;
        if (s[whitecounter] != 'B') i++;
    }


    l sum = 0;

    for (int i = 0; i < s.size(); i++) {
        while (s[i] == 'W') {
            i++;
            if (i >= s.size()) break;
        }
        if (i >= s.size()) break;
        connex[i] = whitecounter;
        connex[whitecounter] = i;
        connections.push_back({i, whitecounter++});
        whitecounter %= 2*n;
        while (s[whitecounter] == 'B') {
            whitecounter++;
            whitecounter %= 2*n;
        }
    }

    l cutting = 1;
    //start
    l white = 0;
    //finish
    l black = 0;
    sum = 0;

    pair<l, l> e;

    l newwhite, newblack;

    for (int i = 0; i < connections.size(); i++) {
        e = connections[i];
        while (white != e.second) {
            newwhite = (white+1)%(n*2);
            if (is_in_range(black, white, connex[newwhite])) cutting--;
            else cutting++;
            white = newwhite;
        }
        while (black != e.first) {
            newblack = black+1;
            if (is_in_range(newblack, white, connex[black])) cutting++;
            else cutting--;
            black = newblack;
        }


        sum += cutting;
    }


    return ceil((float)sum/2.0);
}


int main() {
    cin >> n >> s;

    l c = 0;
    while(s[c] != 'B') c++;
    s = s.substr(c, s.size()-1) + s.substr(0, c);

    l sol = 0;
    l t;
    for (l i = 1<<20; i > 0; i /= 2) {
        //cout << intersections(sol+i) << " " << intersections(sol+i+1) << endl;
        t = intersections(sol+i);
        if (t < intersections(sol+i+1) && t > 0) {
            sol += i;
        }
    }
    while (intersections(sol+2) > intersections(sol+1)) sol++;
    while (intersections(sol) > intersections(sol+1)) sol--;

    cout << intersections(sol+1) << endl;

    return 0;
}

Compilation message

monochrome.cpp: In function 'long long int intersections(long long int)':
monochrome.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < s.size(); i++) {
      |                     ~~^~~~~~~~~~
monochrome.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             if (i >= s.size()) break;
      |                 ~~^~~~~~~~~~~
monochrome.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if (i >= s.size()) break;
      |             ~~^~~~~~~~~~~
monochrome.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < connections.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Halted 0 ms 0 KB -