Submission #885107

#	Time	Username	Problem	Language	Result	Execution time	Memory
885107		VN_AnhTuan	Difference (POI11_roz)	C++17	100 / 100	919 ms	27036 KiB

roz

//  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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10