CSES - Aalto Competitive Programming 2024 - wk9 - Mon - Results
Submission details
Task:Matter++
Sender:AleksandrPolitov
Submission time:2024-11-04 17:18:11 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#50.01 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#80.00 sdetails
#90.00 sdetails
#100.00 sdetails
#110.00 sdetails
#120.00 sdetails
#130.00 sdetails
#140.00 sdetails
#150.00 sdetails
#160.00 sdetails
#170.00 sdetails
#180.00 sdetails
#190.00 sdetails
#200.00 sdetails
#210.00 sdetails
#220.00 sdetails
#230.00 sdetails
#240.00 sdetails
#250.00 sdetails
#260.00 sdetails
#270.00 sdetails
#280.00 sdetails
#290.00 sdetails
#300.00 sdetails
#310.00 sdetails
#320.00 sdetails
#330.00 sdetails
#340.00 sdetails
#350.00 sdetails
#360.00 sdetails
#370.00 sdetails
#380.00 sdetails
#390.00 sdetails
#400.00 sdetails
#410.00 sdetails
#420.00 sdetails
#430.00 sdetails
#440.00 sdetails
#450.00 sdetails
#460.00 sdetails
#470.00 sdetails
#480.00 sdetails
#490.00 sdetails
#500.00 sdetails
#510.00 sdetails
#520.01 sdetails
#530.01 sdetails
#540.01 sdetails
#550.01 sdetails
#560.01 sdetails
#570.01 sdetails
#580.01 sdetails
#590.01 sdetails
#600.01 sdetails
#610.01 sdetails
#620.02 sdetails
#630.02 sdetails
#640.02 sdetails
#650.02 sdetails
#660.02 sdetails
#670.02 sdetails
#680.02 sdetails
#690.02 sdetails
#700.02 sdetails
#710.02 sdetails

Code

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define char unsigned char
#define rep(i, a, b) for(int i=a; i< (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back

#define LSOne(S) ((S) & -(S))

using namespace std;
// mt19937 rnd(239);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> int sgn(T x) { return (T(0) < x) - (x < T(0)); }
typedef long double T;
typedef complex<T> pt;
#define X real()
#define Y imag()

template<class T>
istream& operator>> (istream& is, complex<T>& p) {
    T value;
    is >> value;
    p.real(value);
    is >> value;
    p.imag(value);
    return is;
}

typedef long long ll;
typedef long double ld;

using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}

const int INF = 1e9; // 10^9 = 1B is < 2^31-1
const ll LLINF = 4e18; // 4*10^18 is < 2^63-1
const double EPS = 1e-9;
const ll MOD = 1e9+7;

const int N=1e5+10;
ll pref[N][26];
ll W;


ll calc(int i, int j) {
    vector<int> curr(26, 0);
    for (int q = 0; q < 26; q++) {
        curr[q]=pref[j+1][q]-pref[i][q];
    }

    ll res=0;
    for (int q = 0; q < 26; q++) {
        res+=(curr[q]*curr[q]);
    }

    return res;
}

bool ok(int i, int j) {
     return calc(i, j)>=W;
}



int solve() {
    std::cin >> W;
    string s; cin >> s;
    int n=s.size();

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++) pref[i+1][j]=pref[i][j];
        pref[i+1][s[i]-'a']++;
    }


    ll tmp=0;
    for (int i = 0; i < n; i++) {
        tmp+=(pref[n][i]-pref[0][i])*(pref[n][i]-pref[0][i]);
    }



    

    pair<ll, pair<int,int>> ans={tmp, {0, n-1}};
    for (int i = 0; i < n; i++) {
        int lo=i, hi=n;
        while(lo<hi) {
            int mid=(lo+hi+1)/2;
            if(ok(i, mid)) {
                hi=mid-1;
            } else {
                lo=mid;
            }
        }

        //std::cout << "res: " << i << " " << lo+1 << std::endl;
        if(i-lo<ans.fi && ok(lo+1, i)) {
            ans={calc(i, lo+1), {i, lo+1-i+1}};
        }
    }

    std::cout << s.substr(ans.se.fi,ans.se.se) << std::endl;
    

    
    return 0;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    //cin >> TET;
    for (int i = 1; i <= TET; i++) {
        #ifdef ONPC
            cout << "TEST CASE#" << i << endl;
        #endif
        
        if (solve()) {
            break;
        }

        #ifdef ONPC
            cout << "__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
}

Test details

Test 1

Verdict: ACCEPTED

input
1
e

correct output
e

user output
e

Test 2

Verdict: ACCEPTED

input
1
be

correct output
b

user output
b

Test 3

Verdict: ACCEPTED

input
1
za

correct output
z

user output
z

Test 4

Verdict: ACCEPTED

input
1
po

correct output
p

user output
p

Test 5

Verdict:

input
1
acc

correct output
a

user output
ac

Test 6

Verdict: ACCEPTED

input
2
caa

correct output
ca

user output
ca

Test 7

Verdict: ACCEPTED

input
2
caa

correct output
ca

user output
ca

Test 8

Verdict:

input
2
cced

correct output
cc

user output
cce

Test 9

Verdict:

input
2
ceea

correct output
ce

user output
cee

Test 10

Verdict:

input
1
ccad

correct output
c

user output
cca

Test 11

Verdict:

input
4
ccda

correct output
cc

user output
cda

Test 12

Verdict:

input
1
defdf

correct output
d

user output
defd

Test 13

Verdict:

input
1
fefaa

correct output
f

user output
fefa

Test 14

Verdict:

input
7
bafdf

correct output
bafdf

user output
f

Test 15

Verdict:

input
1
aefba

correct output
a

user output
aefb

Test 16

Verdict:

input
3
cbacc

correct output
cc

user output
cbac

Test 17

Verdict:

input
1
bwvfj

correct output
b

user output
bwvf

Test 18

Verdict:

input
11
caaca

correct output
caaca

user output
a

Test 19

Verdict:

input
4
fuilz

correct output
fuil

user output
lz

Test 20

Verdict:

input
5
acacb

correct output
aca

user output
acb

Test 21

Verdict:

input
4
jnmma

correct output
mm

user output
ma

Test 22

Verdict:

input
6
defdfdfcdd

correct output
defd

user output
defdfdfcd

Test 23

Verdict:

input
5
fefaabfaba

correct output
fef

user output
fefaabfab

Test 24

Verdict:

input
22
bafdfcccbb

correct output
bafdfcccbb

user output
b

Test 25

Verdict:

input
12
aefbaddfcf

correct output
aefbaddf

user output
fcf

Test 26

Verdict:

input
14
cbacccbcba

correct output
cccbc

user output
cbcba

Test 27

Verdict:

input
1
bwvfjxzmcp

correct output
b

user output
bwvfjxzmc

Test 28

Verdict:

input
17
caacaabacb

correct output
aacaa

user output
abacb

Test 29

Verdict:

input
13
fuilzslzio

correct output
ilzslzi

user output
io

Test 30

Verdict:

input
16
acacbbcaba

correct output
acacbbc

user output
caba

Test 31

Verdict:

input
5
jnmmadidaf

correct output
nmm

user output
jnmmadida

Test 32

Verdict:

input
278
defdfdfcddccbfafbcceedcdcffaca...

correct output
fdfcddccbfafbcceedcdcffacadace...

user output
defdfdfcddccbfafbcceedcdcffaca...
Truncated

Test 33

Verdict:

input
32
fefaabfabacbccecfdfcbedbcfbade...

correct output
cbccecfdfc

user output
fefaabfabacbccecfdfcbedbcfbade...
Truncated

Test 34

Verdict:

input
1387
bafdfcccbbabedabcbddedeacddbee...

correct output
dfcccbbabedabcbddedeacddbeebfd...

user output
dbceccecdbfed

Test 35

Verdict:

input
190
aefbaddfcfaaabbaaceaaccdbbcecd...

correct output
aaabbaaceaaccdbbcecdfaedfbccdb...

user output
aefbaddfcfaaabbaaceaaccdbbcecd...
Truncated

Test 36

Verdict:

input
1205
cbacccbcbaacaacacbbcaabcbcbabb...

correct output
abbaabccbacacccbabaabaacccbcbc...

user output
bcccbaaaaabababababbbbbacaabbb...

Test 37

Verdict:

input
299
bwvfjxzmcpktjnmhzevcqtvlgetwch...

correct output
vfjxzmcpktjnmhzevcqtvlgetwchfk...

user output
agsurwfxsaompzbkeviopu

Test 38

Verdict:

input
2796
caacaabacbabbbbbbbcbccbbababcc...

correct output
bacbabbbbbbbcbccbbababccccbbcc...

user output
cbccaacbaccc

Test 39

Verdict:

input
345
fuilzslziogncbkgamnrwuijkbrhrx...

correct output
lziogncbkgamnrwuijkbrhrxsfilyy...

user output
hjxllskkzxueithk

Test 40

Verdict:

input
1517
acacbbcababbcbbbcbcbabccbccbab...

correct output
baaaaaccaaaaababbccbbccaaababb...

user output
bcaaabaabcabbabbaccaabccacbbaa...

Test 41

Verdict:

input
123
jnmmadidafwkdgdckimeiwjytbzsso...

correct output
mmadidafwkdgdckimeiwjytbzssodx...

user output
jnmmadidafwkdgdckimeiwjytbzsso...
Truncated

Test 42

Verdict:

input
1079
defdfdfcddccbfafbcceedcdcffaca...

correct output
fdfdfcddccbfafbcceedcdcffacada...

user output
defdfdfcddccbfafbcceedcdcffaca...
Truncated

Test 43

Verdict:

input
56
fefaabfabacbccecfdfcbedbcfbade...

correct output
fbeeefebaedfff

user output
fefaabfabacbccecfdfcbedbcfbade...
Truncated

Test 44

Verdict:

input
5337
bafdfcccbbabedabcbddedeacddbee...

correct output
bafdfcccbbabedabcbddedeacddbee...

user output
dfcacbfadefdebbcfdddebdffe

Test 45

Verdict:

input
744
aefbaddfcfaaabbaaceaaccdbbcecd...

correct output
cccacdedecabbcdcebdbbcdfddfbeb...

user output
aefbaddfcfaaabbaaceaaccdbbcecd...
Truncated

Test 46

Verdict:

input
10488
cbacccbcbaacaacacbbcaabcbcbabb...

correct output
bcbcbabbcabbaabccbacacccbabaab...

user output
cccaabbccabaacbabcbbbba

Test 47

Verdict:

input
11
bwvfjxzmcpktjnmhzevcqtvlgetwch...

correct output
pxyyy

user output
bwvfjxzmcpktjnmhzevcqtvlgetwch...
Truncated

Test 48

Verdict:

input
5929
caacaabacbabbbbbbbcbccbbababcc...

correct output
bbbbbbbcbccbbababccccbbccccbac...

user output
babccccbcbabcbabaacabbabcbacba...

Test 49

Verdict:

input
1398
fuilzslziogncbkgamnrwuijkbrhrx...

correct output
gncbkgamnrwuijkbrhrxsfilyygatp...

user output
uumxfrwugygbjwkhgmeuksvdurqb

Test 50

Verdict:

input
5219
acacbbcababbcbbbcbcbabccbccbab...

correct output
acbbcababbcbbbcbcbabccbccbabba...

user output
bbbbaaaababcacbabcccacbbcabcca...

Test 51

Verdict:

input
450
jnmmadidafwkdgdckimeiwjytbzsso...

correct output
qmtyjuvzcecnbymqfwyzzergpwuxbt...

user output
jnmmadidafwkdgdckimeiwjytbzsso...
Truncated

Test 52

Verdict:

input
26679
defdfdfcddccbfafbcceedcdcffaca...

correct output
bcbfacacffbedecaafcecffaffaadd...

user output
defdfdfcddccbfafbcceedcdcffaca...
Truncated

Test 53

Verdict:

input
22417
fefaabfabacbccecfdfcbedbcfbade...

correct output
adefccdcafbeeefebaedfffeaeabba...

user output
fefaabfabacbccecfdfcbedbcfbade...
Truncated

Test 54

Verdict:

input
128464
bafdfcccbbabedabcbddedeacddbee...

correct output
bafdfcccbbabedabcbddedeacddbee...

user output
dafdaeccdeadfbbdccccbdaafcecbf...
Truncated

Test 55

Verdict:

input
10769
aefbaddfcfaaabbaaceaaccdbbcecd...

correct output
ebefdceecdabceccdeaebdeebdcdfa...

user output
aefbaddfcfaaabbaaceaaccdbbcecd...
Truncated

Test 56

Verdict:

input
70653
cbacccbcbaacaacacbbcaabcbcbabb...

correct output
acaaaaaabaaabbccbabbbbcacbccbc...

user output
cbacccbcbaacaacacbbcaabcbcbabb...
Truncated

Test 57

Verdict:

input
233
bwvfjxzmcpktjnmhzevcqtvlgetwch...

correct output
qfvyojqjvhyfxtvycrjlaoofuebvev...

user output
bwvfjxzmcpktjnmhzevcqtvlgetwch...
Truncated

Test 58

Verdict:

input
116525
caacaabacbabbbbbbbcbccbbababcc...

correct output
caaabbacabbbabcccbacaaacaaccac...

user output
bacabcbcbbaaabbacbaccccaababbb...
Truncated

Test 59

Verdict:

input
27985
fuilzslziogncbkgamnrwuijkbrhrx...

correct output
uilzslziogncbkgamnrwuijkbrhrxs...

user output
yyxfydbsxjhwimllyfptjfjjxuvgdi...
Truncated

Test 60

Verdict:

input
161959
acacbbcababbcbbbcbcbabccbccbab...

correct output
acacbbcababbcbbbcbcbabccbccbab...

user output
bbccabcaccabaacccbccacbacaccca...
Truncated

Test 61

Verdict:

input
8903
jnmmadidafwkdgdckimeiwjytbzsso...

correct output
uaguxmabjxfuialfmskifofagvsnkn...

user output
jnmmadidafwkdgdckimeiwjytbzsso...
Truncated

Test 62

Verdict:

input
264240357
defdfdfcddccbfafbcceedcdcffaca...

correct output
badeaccfbabfcceaabffecbffcdcfe...

user output
(empty)

Test 63

Verdict:

input
30437082
fefaabfabacbccecfdfcbedbcfbade...

correct output
acdbbfafacdebdefccfbcfcdeecdfd...

user output
(empty)

Test 64

Verdict:

input
1280505429
bafdfcccbbabedabcbddedeacddbee...

correct output
eaceacebbcdfacddcecfceccddfcac...

user output
(empty)

Test 65

Verdict:

input
107609709
aefbaddfcfaaabbaaceaaccdbbcecd...

correct output
bffcffbddbfedcccfcdcdfecbbefbe...

user output
(empty)

Test 66

Verdict:

input
706196896
cbacccbcbaacaacacbbcaabcbcbabb...

correct output
bccbccccacabcacaaabcccbacbcaba...

user output
(empty)

Test 67

Verdict:

input
9966992
bwvfjxzmcpktjnmhzevcqtvlgetwch...

correct output
hljwtcgatnetpvfxeiipnhaarsejbf...

user output
(empty)

Test 68

Verdict:

input
1449002782
caacaabacbabbbbbbbcbccbbababcc...

correct output
acbaabcaababcabcccabcbbaacccca...

user output
(empty)

Test 69

Verdict:

input
275504573
fuilzslziogncbkgamnrwuijkbrhrx...

correct output
lziogncbkgamnrwuijkbrhrxsfilyy...

user output
(empty)

Test 70

Verdict:

input
1480920774
acacbbcababbcbbbcbcbabccbccbab...

correct output
bcccaccabcaabccaaabcbbacbbbbba...

user output
(empty)

Test 71

Verdict:

input
199518168
jnmmadidafwkdgdckimeiwjytbzsso...

correct output
mzdiyihtesgshxbshryvzqghavzgrs...

user output
(empty)