oj.uz

Submission #885107

# Submission time Handle Problem Language Result Execution time Memory
885107 2023-12-09T02:35:50 Z VN_AnhTuan Difference (POI11_roz) C++17
100 / 100
 919 ms 27036 KB 
//  Author : Nguyen Anh Tuan - THPT Chuyen Bac Giang - Train VOI 2023/2024

#include<bits/stdc++.h>
#define file(NAME) {freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout);}
#define foru(i, a, b) for(int i=(a);i<=(b);i++)
#define ford(i, a, b) for(int i=(a);i>=(b);i--)
#define rep(i, n) for(int i=(1);i<=(n);i++)
#define fi first
#define se second
#define mp make_pair
#define SZ(v) ((int)((v).size()))
#define all(v) v.begin(),v.end()
#define RR(X) X.resize(unique(all(X)) - begin(X))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;

namespace IO
{
    #define getchar() (ipos==iend and (iend=(ipos=_ibuf)+fread(_ibuf,1,__bufsize,stdin),ipos==iend)?EOF:*ipos++)
    #define putchar(ch) (opos==oend?fwrite(_obuf,1,__bufsize,stdout),opos=_obuf:0,*opos++=(ch))
    #define __bufsize (1<<20)
    char _ibuf[__bufsize],_obuf[__bufsize],_stk[20];
    char *ipos=_ibuf,*iend=_ibuf,*opos=_obuf,*oend = _obuf+__bufsize,*stkpos = _stk;
    struct END{~END(){fwrite(_obuf,1,opos-_obuf,stdout);}}__;
    inline void read(int &x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void write(int x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
    inline void lread(ll&x)
    {
        register ll f=0,ch;
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
        for(x=0;isdigit(ch);ch=getchar())x=(x<<3ll)+(x<<1ll)+(ch^48);
        x=f?-x:x;
    }
    inline void lwrite(ll x)
    {
        if(x<0)putchar('-'),x=-x;
        while(*++stkpos=x%10^48,x/=10,x);
        while(stkpos!=_stk)putchar(*stkpos--);
    }
};

void maximum(ll &a, ll b) {if(b > a) a = b;}
void minimum(ll &a, ll b) {if(b < a) a = b;}
bool bit(int x, int i) {return (x >> i) & 1;}

//-----------------------------------------------------------------------------------
//      END OF TEMPLATE
//-----------------------------------------------------------------------------------
//      Nguyen Anh Tuan - AnhTuan_BG
//      PRAY FOR VOI 2023
//-----------------------------------------------------------------------------------

const int maxn = 1e6 + 5;
int a[maxn], b[maxn];
int cnt[maxn], n;
int pref[maxn], cntPref[maxn];
vector <int> group[33];

int brute()
{
    int best = 0;
    foru(i, 1, n)
    {
        multiset <int> st;
        foru(c, 0, 25) cnt[c] = 0;

        int mx = 0;
        foru(j, i, n)
        {
            int c = a[j];
            if (st.find(cnt[c]) != st.end()) st.erase(st.find(cnt[c]));
            cnt[c] ++;
            st.insert(cnt[c]);

            int delta = abs(*(st.begin()) - *(--st.end()));
            best = max(best, delta);
        }
    }

    return best;
}

int Calc(int c1, int c2)
{
    vector<int> rem;
    rem.push_back(0);
    int i = 0, j = 0;

    while(i < group[c1].size() && j < group[c2].size())
    {
        int u = group[c1][i], v = group[c2][j];
        if (group[c1][i] < group[c2][j])
        {
            rem.push_back(1);
            i ++;
        }
        else if (group[c1][i] > group[c2][j])
        {
            rem.push_back(-1);
            j ++;
        }
    }

    while(i < group[c1].size())
    {
        rem.push_back(1);
        i ++;
    }

    while (j < group[c2].size())
    {
        rem.push_back(-1);
        j ++;
    }


    int m = rem.size() - 1;
    for (int i = 1; i <= m; i ++) cntPref[i] = cntPref[i-1] + (rem[i] == -1);
    for (int i = 1; i <= m; i ++) pref[i] = pref[i-1] + rem[i];

    j = 0;
    int mn = 2e9, best = 0;
    for (int i = 1; i <= m; i ++)
    {
        while (j < i && cntPref[i] - cntPref[j] > 0)
        {
            mn = min(mn, pref[j]);
            j ++;
        }
        best = max(best, pref[i] - mn);
    }
    return best;
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //file("");

    cin >> n;
    foru(i, 1, n)
    {
        char x;
        cin >> x;
        a[i] = x - 'a';
    }

    foru(i, 1, n) group[a[i]].push_back(i);

    int best = 0;
    foru(c1, 0, 25) foru(c2, 0, 25) if (c1 != c2)
    {
        best = max(best, Calc(c1, c2));
    }
    cout << best;

    return 0;
}

Compilation message

roz.cpp: In function 'void IO::read(int&)':
roz.cpp:31:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   31 |         register ll f=0,ch;
      |                     ^
roz.cpp:31:25: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   31 |         register ll f=0,ch;
      |                         ^~
roz.cpp: In function 'void IO::lread(ll&)':
roz.cpp:44:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   44 |         register ll f=0,ch;
      |                     ^
roz.cpp:44:25: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   44 |         register ll f=0,ch;
      |                         ^~
roz.cpp: In function 'int brute()':
roz.cpp:82:13: warning: unused variable 'mx' [-Wunused-variable]
   82 |         int mx = 0;
      |             ^~
roz.cpp: In function 'int Calc(int, int)':
roz.cpp:104:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     while(i < group[c1].size() && j < group[c2].size())
      |           ~~^~~~~~~~~~~~~~~~~~
roz.cpp:104:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     while(i < group[c1].size() && j < group[c2].size())
      |                                   ~~^~~~~~~~~~~~~~~~~~
roz.cpp:106:13: warning: unused variable 'u' [-Wunused-variable]
  106 |         int u = group[c1][i], v = group[c2][j];
      |             ^
roz.cpp:106:31: warning: unused variable 'v' [-Wunused-variable]
  106 |         int u = group[c1][i], v = group[c2][j];
      |                               ^
roz.cpp:119:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     while(i < group[c1].size())
      |           ~~^~~~~~~~~~~~~~~~~~
roz.cpp:125:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |     while (j < group[c2].size())
      |            ~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 5172 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 9 ms 4444 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 16476 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 621 ms 17880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 915 ms 16748 KB Output is correct
2 Correct 701 ms 15336 KB Output is correct
3 Correct 404 ms 18312 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 16636 KB Output is correct
2 Correct 441 ms 25964 KB Output is correct
3 Correct 425 ms 19160 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 16524 KB Output is correct
2 Correct 433 ms 27036 KB Output is correct
3 Correct 472 ms 19168 KB Output is correct