CSES - Aalto Competitive Programming 2024 - wk9 - Wed - Results
Submission details
Task:Ctrl-F
Sender:aalto2024j_001
Submission time:2024-11-06 16:23:52 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.00 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.00 sdetails
#41ACCEPTED0.00 sdetails
#42ACCEPTED0.00 sdetails
#43ACCEPTED0.00 sdetails
#44ACCEPTED0.00 sdetails
#45ACCEPTED0.00 sdetails
#46ACCEPTED0.00 sdetails
#47ACCEPTED0.00 sdetails
#48ACCEPTED0.00 sdetails
#49ACCEPTED0.00 sdetails
#50ACCEPTED0.00 sdetails
#51ACCEPTED0.00 sdetails
#52ACCEPTED0.00 sdetails
#53ACCEPTED0.00 sdetails
#54ACCEPTED0.00 sdetails
#55ACCEPTED0.00 sdetails
#56ACCEPTED0.00 sdetails
#57ACCEPTED0.00 sdetails
#58ACCEPTED0.00 sdetails
#59ACCEPTED0.00 sdetails
#60ACCEPTED0.00 sdetails
#61ACCEPTED0.00 sdetails
#62ACCEPTED0.00 sdetails
#63ACCEPTED0.00 sdetails
#64ACCEPTED0.00 sdetails
#65ACCEPTED0.00 sdetails
#66ACCEPTED0.00 sdetails
#67ACCEPTED0.00 sdetails
#68ACCEPTED0.00 sdetails
#69ACCEPTED0.00 sdetails
#70ACCEPTED0.00 sdetails
#71ACCEPTED0.00 sdetails
#72ACCEPTED0.00 sdetails
#73ACCEPTED0.00 sdetails
#74ACCEPTED0.00 sdetails
#75ACCEPTED0.00 sdetails
#76ACCEPTED0.00 sdetails
#77ACCEPTED0.00 sdetails
#78ACCEPTED0.00 sdetails
#79ACCEPTED0.00 sdetails
#80ACCEPTED0.00 sdetails
#81ACCEPTED0.00 sdetails
#82ACCEPTED0.00 sdetails
#83ACCEPTED0.00 sdetails
#84ACCEPTED0.01 sdetails
#85ACCEPTED0.01 sdetails
#86ACCEPTED0.01 sdetails
#87ACCEPTED0.01 sdetails
#88ACCEPTED0.01 sdetails
#89ACCEPTED0.01 sdetails
#90ACCEPTED0.01 sdetails
#91ACCEPTED0.01 sdetails
#92ACCEPTED0.01 sdetails
#93ACCEPTED0.01 sdetails

Compiler report

input/code.cpp: In function 'int solve()':
input/code.cpp:108:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         if(z[i]==a.size()) {
input/code.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < res.size(); i++) {
      |                     ~~^~~~~~~~~~~~

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;

int solve() {
    string a,b; std::cin >> a >> b;
    string s=a+"$"+b;
    int n=s.size();
    vector<int> z(n);
    int x=0,y=0;
    for (int i = 1; i < n; i++) {
        z[i]=max(0, min(z[i-x], y-i+1));
        while(i+z[i]<n && s[z[i]]==s[i+z[i]]) {
            x=i;
            y=i+z[i];
            z[i]++;
        }
    }
    vector<int> res;
    for (int i = 1; i < n; i++) {
        if(z[i]==a.size()) {
            res.pb(i-a.size());
        }
    }
    std::cout << res.size() << std::endl;
    for (int i = 0; i < res.size(); i++) {
        std::cout << res[i] << " ";
    }
    std::cout  << 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
q q

correct output
1

user output
1

Test 2

Verdict: ACCEPTED

input
wr wn

correct output
0

user output
0

Test 3

Verdict: ACCEPTED

input
sy sy

correct output
1

user output
1

Test 4

Verdict: ACCEPTED

input
su sub

correct output
1

user output
1

Test 5

Verdict: ACCEPTED

input
nrd yjm

correct output
0

user output
0

Test 6

Verdict: ACCEPTED

input
a bbbb

correct output
0

user output
0

Test 7

Verdict: ACCEPTED

input
mtn mtnr

correct output
1

user output
1

Test 8

Verdict: ACCEPTED

input
bnp lbnpr

correct output
1

user output
1

Test 9

Verdict: ACCEPTED

input
bab aabbb

correct output
0

user output
0

Test 10

Verdict: ACCEPTED

input
aba babab

correct output
1

user output
1

Test 11

Verdict: ACCEPTED

input
aabb bbaab

correct output
0

user output
0

Test 12

Verdict: ACCEPTED

input
gx oqxwd

correct output
0

user output
0

Test 13

Verdict: ACCEPTED

input
noe noemx

correct output
1

user output
1

Test 14

Verdict: ACCEPTED

input
bbbbbabb aaababaaab

correct output
0

user output
0

Test 15

Verdict: ACCEPTED

input
caaac aaababbcbc

correct output
0

user output
0

Test 16

Verdict: ACCEPTED

input
ayoyl mkiiefsqdh

correct output
0

user output
0

Test 17

Verdict: ACCEPTED

input
svhdno xlxadbfgbc

correct output
0

user output
0

Test 18

Verdict: ACCEPTED

input
accc bcbaacaaca

correct output
0

user output
0

Test 19

Verdict: ACCEPTED

input
wvf jxzmcpktjn

correct output
0

user output
0

Test 20

Verdict: ACCEPTED

input
ac aabacbabbb

correct output
1

user output
1

Test 21

Verdict: ACCEPTED

input
l uilzslziog

correct output
2
3 6 

user output
2
3 6 

Test 22

Verdict: ACCEPTED

input
zgwjnvgka pltkknwmyo

correct output
0

user output
0

Test 23

Verdict: ACCEPTED

input
d nmmadidafw

correct output
2
5 7 

user output
2
5 7 

Test 24

Verdict: ACCEPTED

input
amqltvmp amqltvmpfa

correct output
1

user output
1

Test 25

Verdict: ACCEPTED

input
ar mfsykcmfax

correct output
0

user output
0

Test 26

Verdict: ACCEPTED

input
xa twgcnsajxa

correct output
1

user output
1

Test 27

Verdict: ACCEPTED

input
bbb babbabbbbb

correct output
3
6 7 8 

user output
3
6 7 8 

Test 28

Verdict: ACCEPTED

input
bcbaa aacabaabbb

correct output
0

user output
0

Test 29

Verdict: ACCEPTED

input
ba abcacbaaca

correct output
1

user output
1

Test 30

Verdict: ACCEPTED

input
djs nboibdjsfe

correct output
1

user output
1

Test 31

Verdict: ACCEPTED

input
nve xbuukrcqfo

correct output
0

user output
0

Test 32

Verdict: ACCEPTED

input
nlwgexw ftarlzogwa

correct output
0

user output
0

Test 33

Verdict: ACCEPTED

input
i tkgsdgircb

correct output
1

user output
1

Test 34

Verdict: ACCEPTED

input
ccccba bccbcbabca

correct output
0

user output
0

Test 35

Verdict: ACCEPTED

input
bba ababaaabba

correct output
1

user output
1

Test 36

Verdict: ACCEPTED

input
babbb ababaabaaa

correct output
0

user output
0

Test 37

Verdict: ACCEPTED

input
abbabaabaa aaabbaaabb

correct output
0

user output
0

Test 38

Verdict: ACCEPTED

input
sbzifzjntu sbzifzjntu

correct output
1

user output
1

Test 39

Verdict: ACCEPTED

input
aaaaaa aaabbaabaa

correct output
0

user output
0

Test 40

Verdict: ACCEPTED

input
abbbab aaaababbba

correct output
0

user output
0

Test 41

Verdict: ACCEPTED

input
jjhzv vxtmwjjhzv

correct output
1

user output
1

Test 42

Verdict: ACCEPTED

input
ohdekkui naemwyyvzo

correct output
0

user output
0

Test 43

Verdict: ACCEPTED

input
ba ccbbabaccc

correct output
2
4 6 

user output
2
4 6 

Test 44

Verdict: ACCEPTED

input
qltvmpfafstgegcdrryvainxvfpasw...

correct output
1

user output
1

Test 45

Verdict: ACCEPTED

input
armfsykcmfaxmvycwxs scnxuwpetq...

correct output
0

user output
0

Test 46

Verdict: ACCEPTED

input
iazfqzyetdvokklp twgcnsajxaxha...

correct output
1
63 

user output
1
63 

Test 47

Verdict: ACCEPTED

input
bbb babbabbbbbbabaabababbaaaba...

correct output
14
6 7 8 9 52 53 58 59 64 76 77 7...

user output
14
6 7 8 9 52 53 58 59 64 76 77 7...

Test 48

Verdict: ACCEPTED

input
bcbaa aacabaabbbaccbbabcaacaaa...

correct output
0

user output
0

Test 49

Verdict: ACCEPTED

input
ba abcacbaacacaaaccaabcbcccbac...

correct output
11
6 25 38 44 51 70 72 77 92 94 9...

user output
11
6 25 38 44 51 70 72 77 92 94 9...

Test 50

Verdict: ACCEPTED

input
boibdjsferqewbvyroecpso nboibd...

correct output
1

user output
1

Test 51

Verdict: ACCEPTED

input
nvexbuukrcqfoqbwjbytbowawfbmqh...

correct output
0

user output
0

Test 52

Verdict: ACCEPTED

input
nlwgexwftarlzogwazqiwotpahcqhf...

correct output
0

user output
0

Test 53

Verdict: ACCEPTED

input
xjjeioibiv tkgsdgircbrduazzqpf...

correct output
1
66 

user output
1
66 

Test 54

Verdict: ACCEPTED

input
ccccba bccbcbabcacaccccbcccaac...

correct output
0

user output
0

Test 55

Verdict: ACCEPTED

input
bba ababaaabbaabbaaabaabaaaabb...

correct output
11
8 12 26 30 37 42 66 72 82 88 9...

user output
11
8 12 26 30 37 42 66 72 82 88 9...

Test 56

Verdict: ACCEPTED

input
babbb ababaabaaabbaabababbaaaa...

correct output
2
46 61 

user output
2
46 61 

Test 57

Verdict: ACCEPTED

input
abbabaabaa aaabbaaabbbbaabbabb...

correct output
0

user output
0

Test 58

Verdict: ACCEPTED

input
sbzifzjntuzmiqdhjoiajrskxxntgh...

correct output
1

user output
1

Test 59

Verdict: ACCEPTED

input
aaaaaa aaabbaabaababaaabbaabbb...

correct output
0

user output
0

Test 60

Verdict: ACCEPTED

input
abbbab aaaababbbaaabbaaabaabab...

correct output
0

user output
0

Test 61

Verdict: ACCEPTED

input
ghauoeqbgszeeppknnlffspwvyytbm...

correct output
1
40 

user output
1
40 

Test 62

Verdict: ACCEPTED

input
ohdekkuinaemwyyvzofxzwgwaryuxm...

correct output
0

user output
0

Test 63

Verdict: ACCEPTED

input
ba ccbbabaccccccccaacaabbbbaaa...

correct output
9
4 6 24 35 54 72 76 83 91 

user output
9
4 6 24 35 54 72 76 83 91 

Test 64

Verdict: ACCEPTED

input
qltvmpfafstgegcdrryvainxvfpasw...

correct output
1

user output
1

Test 65

Verdict: ACCEPTED

input
armfsykcmfaxmvycwxsscnxuwpetqr...

correct output
0

user output
0

Test 66

Verdict: ACCEPTED

input
ljsoejwqaebfjygmnrdcqoowvcgsei...

correct output
1
569 

user output
1
569 

Test 67

Verdict: ACCEPTED

input
bbb babbabbbbbbabaabababbaaaba...

correct output
122
6 7 8 9 52 53 58 59 64 76 77 7...

user output
122
6 7 8 9 52 53 58 59 64 76 77 7...

Test 68

Verdict: ACCEPTED

input
bcbaa aacabaabbbaccbbabcaacaaa...

correct output
2
128 811 

user output
2
128 811 

Test 69

Verdict: ACCEPTED

input
ba abcacbaacacaaaccaabcbcccbac...

correct output
115
6 25 38 44 51 70 72 77 92 94 9...

user output
115
6 25 38 44 51 70 72 77 92 94 9...

Test 70

Verdict: ACCEPTED

input
xbdpqykclzyjerkdnyfqrynxbloyps...

correct output
1
174 

user output
1
174 

Test 71

Verdict: ACCEPTED

input
nvexbuukrcqfoqbwjbytbowawfbmqh...

correct output
0

user output
0

Test 72

Verdict: ACCEPTED

input
nlwgexwftarlzogwazqiwotpahcqhf...

correct output
0

user output
0

Test 73

Verdict: ACCEPTED

input
dqzgitxhpsubvrsocoxjjeioibivfs...

correct output
1
48 

user output
1
48 

Test 74

Verdict: ACCEPTED

input
ccccba bccbcbabcacaccccbcccaac...

correct output
3
229 277 593 

user output
3
229 277 593 

Test 75

Verdict: ACCEPTED

input
bba ababaaabbaabbaaabaabaaaabb...

correct output
121
8 12 26 30 37 42 66 72 82 88 9...

user output
121
8 12 26 30 37 42 66 72 82 88 9...

Test 76

Verdict: ACCEPTED

input
babbb ababaabaaabbaabababbaaaa...

correct output
29
46 61 118 126 252 318 330 350 ...

user output
29
46 61 118 126 252 318 330 350 ...

Test 77

Verdict: ACCEPTED

input
abbabaabaa aaabbaaabbbbaabbabb...

correct output
2
167 584 

user output
2
167 584 

Test 78

Verdict: ACCEPTED

input
yxlvjhoqnrjzixyyxqypyfcmeujvyn...

correct output
1
36 

user output
1
36 

Test 79

Verdict: ACCEPTED

input
aaaaaa aaabbaabaababaaabbaabbb...

correct output
16
147 148 222 223 224 225 303 30...

user output
16
147 148 222 223 224 225 303 30...

Test 80

Verdict: ACCEPTED

input
abbbab aaaababbbaaabbaaabaabab...

correct output
13
208 278 449 539 572 637 698 82...

user output
13
208 278 449 539 572 637 698 82...

Test 81

Verdict: ACCEPTED

input
tkjzptqkkzkyuknjbtdhbxzbvdynoe...

correct output
1
398 

user output
1
398 

Test 82

Verdict: ACCEPTED

input
ohdekkuinaemwyyvzofxzwgwaryuxm...

correct output
0

user output
0

Test 83

Verdict: ACCEPTED

input
ba ccbbabaccccccccaacaabbbbaaa...

correct output
106
4 6 24 35 54 72 76 83 91 120 1...

user output
106
4 6 24 35 54 72 76 83 91 120 1...

Test 84

Verdict: ACCEPTED

input
uimfxocfupiquprsfvwrktflasqzwg...

correct output
1
12309 

user output
1
12309 

Test 85

Verdict: ACCEPTED

input
armfsykcmfaxmvycwxsscnxuwpetqr...

correct output
0

user output
0

Test 86

Verdict: ACCEPTED

input
bvifyeheqbketqmweyvfwxslczpinq...

correct output
1
72135 

user output
1
72135 

Test 87

Verdict: ACCEPTED

input
bbb babbabbbbbbabaabababbaaaba...

correct output
12448
6 7 8 9 52 53 58 59 64 76 77 7...

user output
12448
6 7 8 9 52 53 58 59 64 76 77 7...

Test 88

Verdict: ACCEPTED

input
bcbaa aacabaabbbaccbbabcaacaaa...

correct output
415
128 811 1185 1404 1540 1595 18...

user output
415
128 811 1185 1404 1540 1595 18...

Test 89

Verdict: ACCEPTED

input
ba abcacbaacacaaaccaabcbcccbac...

correct output
22302
6 25 38 44 51 70 72 77 92 94 9...

user output
22302
6 25 38 44 51 70 72 77 92 94 9...

Test 90

Verdict: ACCEPTED

input
hdoncwccngxcinaaxlqqaqeeddicpb...

correct output
1
25985 

user output
1
25985 

Test 91

Verdict: ACCEPTED

input
nvexbuukrcqfoqbwjbytbowawfbmqh...

correct output
0

user output
0

Test 92

Verdict: ACCEPTED

input
nlwgexwftarlzogwazqiwotpahcqhf...

correct output
0

user output
0

Test 93

Verdict: ACCEPTED

input
psvihsxqpawhwrzhxgbpkgaeoxkrtp...

correct output
1
108381 

user output
1
108381