Submission #1032379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032379		Andrey	Monochrome Points (JOI20_monochrome)	C++14	35 / 100	2061 ms	6088 KiB

monochrome

#include<bits/stdc++.h>
using namespace std;

int sb = 0;

vector<int> calc(vector<int> haha, int br) {
    if(br == 0) {
        return haha;
    }
    sb+=br*(br-1)/2;
    int p1 = haha.size(),p2 = -1,z = 0;
    vector<int> ans(0);
    for(int i = 0; i < haha.size(); i++) {
        if(haha[i] == 1) {
            sb-=i;
            z++;
            haha[i] = 2;
            if(z == br) {
                p1 = i;
                break;
            }
        }
    }
    z = 0;
    for(int i = (int)haha.size()-1; i >= 0; i--) {
        if(haha[i] == 0) {
            z++;
            sb+=i-1-(br-z)*2;
            haha[i] = 2;
            if(z == br) {
                p2 = i;
                break;
            }
        }
    }
    if(p1 < p2) {
        for(int i = 0; i < haha.size(); i++) {
            if(haha[i] != 2) {
                ans.push_back(haha[i]);
            }
        }
        return ans;
    }
    else {
        sb = -1;
        return ans;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int ans = 0;
    int n;
    cin >> n;
    vector<int> haha(2*n);
    char a;
    for(int i = 0; i < 2*n; i++) {
        cin >> a;
        if(a == 'W') {
            haha[i] = 0;
        }
        else {
            haha[i] = 1;
        }
    }
    if(haha[0] == 1) {
        for(int i = 0; i < 2*n; i++) {
            haha[i] = 1-haha[i];
        }
    }
    for(int i = 1; i < 2*n; i++) {
        if(haha[i]) {
            sb = 0;
            vector<int> a(0);
            vector<int> b(0);
            for(int j = 1; j < i; j++) {
                a.push_back(haha[j]);
            }
            for(int j = i+1; j < 2*n; j++) {
                b.push_back(haha[j]);
            }
            int c = abs((int)a.size()-(int)b.size())/2;
            sb+=min(a.size(),b.size());
            if(a.size() > b.size()) {
                a = calc(a,c);
            }
            else {
                for(int j = 0; j < b.size(); j++) {
                    b[j] = 1-b[j];
                }
                b = calc(b,c);
                for(int j = 0; j < b.size(); j++) {
                    b[j] = 1-b[j];
                }
            }
            if(sb == -1) {
                continue;
            }
            int y = 0;
            vector<int> p(a.size());
            for(int j = 0; j < a.size(); j++) {
                if(a[j]) {
                    while(b[y] == true) {
                        y++;
                    }
                    p[j] = y;
                    y++;
                }
            }
            y = 0;
            for(int j = 0; j < a.size(); j++) {
                if(!a[j]) {
                    while(b[y] == false) {
                        y++;
                    }
                    p[j] = y;
                    y++;
                }
            }
            for(int j = 0; j < a.size(); j++) {
                for(int k = j+1; k < a.size(); k++) {
                    if(p[k] > p[j]) {
                        sb++;
                    }
                }
            }
            ans = max(ans,sb);
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

monochrome.cpp: In function 'std::vector<int> calc(std::vector<int>, int)':
monochrome.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < haha.size(); i++) {
      |                    ~~^~~~~~~~~~~~~
monochrome.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for(int i = 0; i < haha.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
monochrome.cpp: In function 'int main()':
monochrome.cpp:91:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                 for(int j = 0; j < b.size(); j++) {
      |                                ~~^~~~~~~~~~
monochrome.cpp:95:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                 for(int j = 0; j < b.size(); j++) {
      |                                ~~^~~~~~~~~~
monochrome.cpp:104:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int j = 0; j < a.size(); j++) {
      |                            ~~^~~~~~~~~~
monochrome.cpp:114:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for(int j = 0; j < a.size(); j++) {
      |                            ~~^~~~~~~~~~
monochrome.cpp:123:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |             for(int j = 0; j < a.size(); j++) {
      |                            ~~^~~~~~~~~~
monochrome.cpp:124:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |                 for(int k = j+1; k < a.size(); k++) {
      |                                  ~~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 0 / 65