Submission #411407

#	Time	Username	Problem	Language	Result	Execution time	Memory
411407		iulia2100	Monochrome Points (JOI20_monochrome)	C++14	25 / 100	2068 ms	324 KiB

monochrome

#include <iostream>

using namespace std;

const int N = 2e5 + 5;

int n;
int alb[N], neg[N], al, ng;
pair <int, int> muchie[N];

//bool idk4(int x, int a, int b)   {
//    if (a < b)
//        swap(a, b);
//    if (idk5() && x < b)
//        return true;
//    return false;
//}

int intersectie(int i,int j){
    int a=muchie[i].first;
    int b=muchie[i].second;
    int c=muchie[j].first;
    int d=muchie[j].second;
    if(a<b)
        swap(a,b);
    if((a>c and c>b) and (a>d and d>b))
        return false;
    if((a<d or d<b) and (a<c or c<b))
        return false;
    return 1;
//    if (idk4(a1, a2, b2) == idk4(b1, a2, b2))
//        return 0;
//    return 1;
}
int idk2(int a){
    if(a<=n)
        return a;
    a-=n;
    return a;
}
int idk(int x)  {
    for(int i=1;i<=n;i++){
        muchie[i]=make_pair(alb[i],neg[idk2(i+x-1)]);
    }
    int cnt = 0;
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cnt+=intersectie(i,j);
        }
    }
    return cnt;
}

int main()  {
    cin >> n;
    char c;
    int a, ans = 0;
    for (int i = 1; i <= n + n; ++i)    {
        cin >> c;
        a = (c == 'B');
        if(a==0){
            alb[++al]=i;
        } else    {
            neg[++ng] = i;
        }
    }
    for (int i = 1; i <= n; ++i)    {
        ans = max(ans, idk(i));
    }
    cout << ans;
    return 0;
}

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