Submission #837063


Source Code Expand

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

const int maxn = 1e5+100;

char s[maxn];
int sum[maxn][26];

int Minpos[26];

void solve(int len,int& resL,int& resR)
{
    for(int i = 1;i <= len;++i)
    {
        int w = s[i]-'a';
        sum[i][w]++;
        for(int j = 0;j < 26;++j)
        {
            sum[i][j] += sum[i-1][j];

            if(i == 1) continue;
            int prv = Minpos[j];
            int valprv = 2*sum[prv][j]-prv;
            int now = 2*sum[i][j]-i;
            if(now > valprv)
            {
                resL = prv+1;
                resR = i;
                return;
            }

        }

        for(int j = 0;j < 26;++j)
        {
            int prv = Minpos[j];
            int valprv = 2*sum[prv][j]-prv;

            int now = 2*sum[i-1][j]-(i-1);

            if(valprv > now)
            {
                Minpos[j] = i-1;
            }
        }

    }


}


int main()
{
   // freopen("./test.txt","r",stdin);
    scanf("%s",s+1);
    int len = strlen(s+1);
    memset(sum,0,sizeof(sum));
    memset(Minpos,0,sizeof(Minpos));
    int resL = -1,resR = -1;
    solve(len,resL,resR);
    printf("%d %d\n",resL,resR);

    return 0;
}

Submission Info

Submission Time
Task D - Unbalanced
User wumpus
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1247 Byte
Status AC
Exec Time 45 ms
Memory 10496 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",s+1);
                    ^

Judge Result

Set Name Sample Sub1 Sub2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 14
AC × 24
Set Name Test Cases
Sample 0_01, 0_02
Sub1 0_01, 0_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14
Sub2 0_01, 0_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 2_15, 2_16, 2_17, 2_18, 2_19, 2_20, 2_21, 2_22, 2_23, 2_24
Case Name Status Exec Time Memory
0_01 AC 18 ms 10368 KB
0_02 AC 22 ms 10368 KB
1_03 AC 21 ms 10368 KB
1_04 AC 20 ms 10368 KB
1_05 AC 18 ms 10368 KB
1_06 AC 20 ms 10368 KB
1_07 AC 20 ms 10368 KB
1_08 AC 20 ms 10368 KB
1_09 AC 21 ms 10368 KB
1_10 AC 20 ms 10368 KB
1_11 AC 20 ms 10368 KB
1_12 AC 20 ms 10368 KB
1_13 AC 20 ms 10368 KB
1_14 AC 20 ms 10368 KB
2_15 AC 28 ms 10496 KB
2_16 AC 38 ms 10496 KB
2_17 AC 36 ms 10496 KB
2_18 AC 36 ms 10496 KB
2_19 AC 21 ms 10496 KB
2_20 AC 28 ms 10496 KB
2_21 AC 19 ms 10496 KB
2_22 AC 40 ms 10496 KB
2_23 AC 43 ms 10496 KB
2_24 AC 45 ms 10496 KB