QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305922#7406. Longest Lyndon PrefixKLPP#AC ✓43ms8592kbC++205.8kb2024-01-16 06:08:042024-01-16 06:08:05

Judging History

你现在查看的是最新测评结果

  • [2024-01-16 06:08:05]
  • 评测
  • 测评结果:AC
  • 用时:43ms
  • 内存:8592kb
  • [2024-01-16 06:08:04]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

/*
 * Time Complexity: Suffix Array: O(N + Character_Set_Size) time and space //
 128 --- ASCII
 *                  LCP: O(N) time and space
 * Usage:
 *       1. Suffix Array (returns s.size() elements, NOT considering
 0-length/empty suffix)
 *             auto sa = suffix_array(s); // s is the input string with ASCII
 characters
 *             auto sa_wide_char = suffix_array(s, LIM); // LIM = max(s[i]) + 2,
 s is the string with arbitary big characters.
 *       2. LCP:
 *            auto lcp = LCP(s, suffix_array(s)); // returns s.size() elements,
 where lcp[i]=LCP(sa[i], sa[i+1])
 */
void induced_sort(const std::vector<int>& vec, int val_range,
                  std::vector<int>& SA, const std::vector<bool>& sl,
                  const std::vector<int>& lms_idx) {
    std::vector<int> l(val_range, 0), r(val_range, 0);
    for (int c : vec) {
        if (c + 1 < val_range) ++l[c + 1];
        ++r[c];
    }
    std::partial_sum(l.begin(), l.end(), l.begin());
    std::partial_sum(r.begin(), r.end(), r.begin());
    std::fill(SA.begin(), SA.end(), -1);
    for (int i = (int)lms_idx.size() - 1; i >= 0; --i)
        SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
    for (int i : SA)
        if (i >= 1 && sl[i - 1]) SA[l[vec[i - 1]]++] = i - 1;
    std::fill(r.begin(), r.end(), 0);
    for (int c : vec) ++r[c];
    std::partial_sum(r.begin(), r.end(), r.begin());
    for (int k = (int)SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
        if (i >= 1 && !sl[i - 1]) {
            SA[--r[vec[i - 1]]] = i - 1;
        }
}
std::vector<int> SA_IS(const std::vector<int>& vec, int val_range) {
    const int n = vec.size();
    std::vector<int> SA(n), lms_idx;
    std::vector<bool> sl(n);
    sl[n - 1] = false;
    for (int i = n - 2; i >= 0; --i) {
        sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
        if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
    }
    std::reverse(lms_idx.begin(), lms_idx.end());
    induced_sort(vec, val_range, SA, sl, lms_idx);
    std::vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
    for (int i = 0, k = 0; i < n; ++i)
        if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
            new_lms_idx[k++] = SA[i];
        }
    int cur = 0;
    SA[n - 1] = cur;
    for (size_t k = 1; k < new_lms_idx.size(); ++k) {
        int i = new_lms_idx[k - 1], j = new_lms_idx[k];
        if (vec[i] != vec[j]) {
            SA[j] = ++cur;
            continue;
        }
        bool flag = false;
        for (int a = i + 1, b = j + 1;; ++a, ++b) {
            if (vec[a] != vec[b]) {
                flag = true;
                break;
            }
            if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
                flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
                break;
            }
        }
        SA[j] = (flag ? ++cur : cur);
    }
    for (size_t i = 0; i < lms_idx.size(); ++i) lms_vec[i] = SA[lms_idx[i]];
    if (cur + 1 < (int)lms_idx.size()) {
        auto lms_SA = SA_IS(lms_vec, cur + 1);
        for (size_t i = 0; i < lms_idx.size(); ++i) {
            new_lms_idx[i] = lms_idx[lms_SA[i]];
        }
    }
    induced_sort(vec, val_range, SA, sl, new_lms_idx);
    return SA;
}
std::vector<int> suffix_array(const std::string& s, const char first = 'a',
                         const char last = 'z') {
    std::vector<int> vec(s.size() + 1);
    std::copy(std::begin(s), std::end(s), std::begin(vec));
    for (auto& x : vec) x -= (int)first - 1;
    vec.back() = 0;
    auto ret = SA_IS(vec, (int)last - (int)first + 2);
    ret.erase(ret.begin());
    return ret;
}
// Uses kasai's algorithm linear in time and space
std::vector<int> LCP(const std::string& s, const std::vector<int>& sa) {
    int n = s.size(), k = 0;
    std::vector<int> lcp(n), rank(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    for (int i = 0; i < n; i++, k ? k-- : 0) {
        if (rank[i] == n - 1) {
            k = 0;
            continue;
        }
        int j = sa[rank[i] + 1];
        while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
        lcp[rank[i]] = k;
    }
    lcp[n - 1] = 0;
    return lcp;
}
const int MAX=1000000;
const lld INF=1e18;
class ST{
	lld arr[4*MAX];
	public:
	void build(int a, int b, int node){
		arr[node]=-INF;
		if(a==b){
			return;
		}
		int mid=(a+b)/2;
		build(a,mid,2*node);
		build(mid+1,b,2*node+1);
	}
	void update(int a, int b, int node, int pos, lld val){
		if(pos<a || b<pos)return;
		if(a==b){
			arr[node]=val;
			return;
		}
		int mid=(a+b)/2;
		update(a,mid,2*node,pos,val);
		update(mid+1,b,2*node+1,pos,val);
		arr[node]=max(arr[2*node],arr[2*node+1]);
	}
	lld query(int a, int b, int node, int l, int r){
		if(r<a || b<l)return -INF;
		if(l<=a && b<=r)return arr[node];
		int mid=(a+b)/2;
		return max(query(a,mid,2*node,l,r),query(mid+1,b,2*node+1,l,r));
	}
};
ST S;
void solve(){
	int n;
	string s;
	cin>>n>>s;
	S.build(0,n-1,1);
	vector<int> SA=suffix_array(s);
	vector<pair<int,int> >V;
	rep(i,0,n){
		V.push_back({SA[i],i});
	}
	sort(V.begin(),V.end());
	vector<lld> res;
	for(int i=n-1;i>-1;i--){
		int pos=V[i].second;
		lld ans=min((lld)n,-S.query(0,n-1,1,0,pos));
		S.update(0,n-1,1,pos,-i);
		res.push_back(ans-i);
	}
	reverse(res.begin(),res.end());
	trav(a,res)cout<<a<<" ";
	cout<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--){
		solve();
	}
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

3
3
aaa
3
aab
3
cba

output:

1 1 1 
3 2 1 
1 1 1 

result:

ok 9 numbers

Test #2:

score: 0
Accepted
time: 12ms
memory: 3876kb

input:

10000
10
ababbbbaaa
6
aabbaa
3
abb
9
bababbbbb
9
abbaaaaaa
8
ababbaab
7
abbbbbb
7
aaabaaa
2
ba
10
abaababbab
2
ab
1
a
1
a
5
ababa
6
aaabba
2
ba
4
abba
5
bbbba
9
aabbbbbaa
10
baaabaaaba
10
babbbbbbaa
9
babaaabba
1
b
6
abbbaa
7
aaaaaab
10
baaaaabaaa
9
bbbbabbba
3
bbb
8
abaababa
7
bbbbaba
5
ababb
1
b
7...

output:

7 1 5 1 1 1 1 1 1 1 
4 3 1 1 1 1 
3 1 1 
1 8 1 6 1 1 1 1 1 
3 1 1 1 1 1 1 1 1 
5 1 3 1 1 3 2 1 
7 1 1 1 1 1 1 
4 3 2 1 1 1 1 
1 1 
2 1 8 5 1 3 1 1 2 1 
2 1 
1 
1 
2 1 2 1 1 
5 4 3 1 1 1 
1 1 
3 1 1 1 
1 1 1 1 1 
7 6 1 1 1 1 1 1 1 
1 4 3 2 1 4 3 2 1 1 
1 7 1 1 1 1 1 1 1 1 
1 2 1 5 4 3 1 1 1 
1 
4 1 1...

result:

ok 54963 numbers

Test #3:

score: 0
Accepted
time: 13ms
memory: 3680kb

input:

10000
4
cbcc
7
cccbcac
3
cac
3
cba
6
caaacb
9
aaabaccac
8
acbabbab
7
cbabcac
2
ba
4
caab
4
bcac
8
aacabcac
8
cbbbacab
7
cbcacca
4
aaac
3
bac
10
acacbabaab
6
ccabba
6
cbccca
5
cbabb
9
acacbcbba
1
c
9
aaacacaba
10
aacbaaacbc
5
bbaac
8
bbaabbab
3
bac
3
cbb
3
caa
3
abb
2
bc
8
abcacbca
6
bbabab
5
bcbca
1...

output:

1 3 1 1 
1 1 1 2 1 2 1 
1 2 1 
1 1 1 
1 5 4 3 1 1 
9 8 7 1 3 1 1 2 1 
3 1 1 3 1 1 2 1 
1 1 5 2 1 2 1 
1 1 
1 3 2 1 
2 1 2 1 
8 2 1 5 2 1 2 1 
1 1 1 1 2 1 2 1 
1 2 1 3 1 1 1 
4 3 2 1 
1 2 1 
5 1 3 1 1 2 1 3 2 1 
1 1 3 1 1 1 
1 4 1 1 1 1 
1 1 3 1 1 
8 1 6 1 2 1 1 1 1 
1 
8 7 2 1 2 1 2 1 1 
4 3 1 1 6 5...

result:

ok 54644 numbers

Test #4:

score: 0
Accepted
time: 13ms
memory: 3624kb

input:

10000
8
fddfiagb
5
cabjf
9
cgcbjbdfd
1
a
1
j
3
gcg
3
gba
7
cagdcfh
6
jaidja
2
fh
5
iefej
1
c
7
ggdghae
8
aeaibgge
6
bgihie
9
dhafgiief
6
bhcjih
7
iaajfhe
1
g
1
h
2
hb
3
bac
6
gfdcgc
4
fiad
9
gchaceeaj
10
agjacfdggg
9
bbhiffbgg
8
eeeefjcf
7
afcgiea
2
gj
8
gbiijidi
1
b
6
jejdea
3
fcc
6
ghaijb
10
cecgd...

output:

1 4 3 2 1 3 1 1 
1 4 3 1 1 
2 1 1 2 1 4 2 1 1 
1 
1 
1 2 1 
1 1 1 
1 6 1 1 3 2 1 
1 4 1 2 1 1 
2 1 
1 4 1 2 1 
1 
1 1 3 2 1 2 1 
8 1 6 1 4 1 1 1 
6 4 1 2 1 1 
2 1 7 4 3 1 1 2 1 
6 1 4 1 1 1 
1 6 5 1 2 1 1 
1 
1 
1 1 
1 2 1 
1 1 1 2 1 1 
2 1 2 1 
1 2 1 6 3 1 1 2 1 
3 2 1 7 6 1 4 1 1 1 
9 5 2 1 1 1 3 ...

result:

ok 54830 numbers

Test #5:

score: 0
Accepted
time: 13ms
memory: 3708kb

input:

10000
6
wjgjli
2
um
10
ztmekuwlby
10
waawouorxc
7
juqxdzu
5
kimcu
6
euxxiw
5
uizus
7
wpuyrwg
8
tsdbixbu
8
qsparfin
3
jwn
5
pbiul
9
dcglefecs
1
u
7
sprjnyj
10
npiglkutgk
3
ihv
10
hkjelyarxa
9
abswbhkuw
9
ngohupqot
2
am
3
aax
7
lfpljzo
6
kgetfz
5
wbvwv
6
indqlw
3
qym
4
sddd
2
mt
7
klzloba
9
myifxnhkw
...

output:

1 1 4 2 1 1 
1 1 
1 1 1 5 4 2 1 1 2 1 
1 9 8 1 2 1 3 2 1 1 
4 1 2 1 3 1 1 
1 2 1 2 1 
6 3 1 1 2 1 
1 4 1 1 1 
1 5 2 1 2 1 1 
1 1 1 5 2 1 2 1 
2 1 1 5 1 3 2 1 
3 1 1 
1 4 3 1 1 
1 8 2 1 2 1 1 2 1 
1 
1 2 1 3 2 1 1 
2 1 1 5 1 3 1 1 2 1 
1 2 1 
3 1 1 3 2 1 3 2 1 1 
9 3 2 1 5 4 3 2 1 
1 8 1 6 1 2 1 2 1 ...

result:

ok 55358 numbers

Test #6:

score: 0
Accepted
time: 11ms
memory: 3744kb

input:

1000
23
jdefdahaejiebhbbachgbea
10
eccjdgfdfd
45
aggeechjbaabeccaghcehahgeadahaececgghgijiajdh
32
bgfafgbhechfjbcjadcdbabhgbdgcehf
49
jcabigjdhfaagahjihebibffdebhdgjeiiijjacahiaggcibg
17
gifciaaaechbehbie
82
bcdegeehagadfhfagajfibiegifcfjddibhjhifceijjgedadgighaffcjehaihahcddbjjhghghieafec
88
jiieba...

output:

1 3 2 1 1 2 1 9 3 1 1 1 2 1 1 1 6 3 1 1 2 1 1 
1 9 8 1 3 1 1 2 1 1 
9 1 1 1 1 3 2 1 1 36 35 4 1 1 1 10 2 1 3 2 1 4 1 1 1 20 1 2 1 16 1 10 1 8 7 6 1 4 2 1 1 4 1 2 1 
3 1 1 13 2 1 7 1 1 4 1 2 1 3 2 1 5 1 2 1 1 11 3 1 1 7 2 1 4 3 1 1 
1 1 8 7 1 2 1 3 1 1 39 26 1 24 3 1 1 1 1 2 1 16 1 1 2 1 11 1 9 2 1 6...

result:

ok 52575 numbers

Test #7:

score: 0
Accepted
time: 13ms
memory: 3812kb

input:

100
958
bcaegajcfehihhaijijiagcdhchdgacaiffhcgeacceefbfedebddghdefjjchabccdfdhfafihcjcjhdjbhhaeececaiebiejahgdceicfbdcaegjjaecbfhiegabhcbbjgibhdaeegaffefjfjbhiaiccaccicigfjdjabfdagbdbbbahddfjbgfcgdccgehcijfhjeahefbcjfedacdghjbcedigcijihbajfcfeejgedebcjcgjfbaiabcbcciejehbhjegfagajdaedhijjfiaigifgheff...

output:

2 1 27 2 1 9 1 7 1 5 2 1 1 1 6 2 1 2 1 1 9 1 7 2 1 4 1 2 1 33 1 8 1 3 2 1 3 1 1 23 5 4 3 2 1 5 1 1 2 1 12 9 3 2 1 5 4 3 1 1 2 1 189 8 7 6 5 1 3 1 1 14 3 1 1 7 1 5 1 1 2 1 3 1 1 30 1 1 2 1 1 7 1 1 4 1 2 1 12 1 1 1 5 2 1 2 1 3 1 1 5 4 3 1 1 9 1 1 6 3 2 1 2 1 42 3 1 1 8 4 1 2 1 3 1 1 19 3 2 1 15 1 1 5 ...

result:

ok 52113 numbers

Test #8:

score: 0
Accepted
time: 12ms
memory: 3844kb

input:

100
917
urldtufacwbinfdubedmcwhgopzwzdgctwdxzdpkjdvsjqwhfmxlbjaniolzgfjetehrqvcvxmbpkcgccxteriwvzuhflkbhqkzzqcuodovddiitnmjnptqpnrvoqdhvpcvbzqejvkecwaynsuqkvbubwouwrmzqqlkelnculupjheobidrworymefjhvggxeofaksrokysyrnndbfcwsntyvcojnoyumlalojfjvtfejqcbvjlizdyneegubsfucawlurjletoyjfxegalalcnytyjjjiwzkbkc...

output:

1 1 1 4 2 1 1 746 2 1 6 2 1 1 2 1 38 1 2 1 11 1 1 6 5 4 1 2 1 2 1 21 2 1 3 2 1 15 1 1 1 11 1 1 3 2 1 1 4 2 1 1 2 1 141 1 4 1 2 1 1 2 1 2 1 5 4 1 2 1 4 2 1 1 20 1 1 2 1 15 14 1 1 11 1 5 1 2 1 1 1 3 1 1 47 6 1 4 1 1 1 30 1 1 3 2 1 22 17 16 15 1 1 1 11 10 3 1 1 1 5 2 1 2 1 4 3 1 1 2 1 10 1 1 4 3 1 1 1 ...

result:

ok 48866 numbers

Test #9:

score: 0
Accepted
time: 36ms
memory: 8472kb

input:

1
100000
bbbabaabaaabaabbbabaababbabbbabaaaababbabaababbaababbabbbbaaababbaaaaabaabbbabbbaababaabbaabbababbabbabababbaaaabbabbbbbbbbbbabaabbbabbbaaaabaaaaaabbbaababaaabbaabaabbaabbaaabababbaabbaaaaaabbbaaabaababbbbbaaaabbaababaabbbbbbabababaabababaaaabbbbbbaabbbabaaaabbbababaaaabbaaaaaabbabaaabaabba...

output:

1 1 1 2 1 3 2 1 23 22 2 1 7 4 1 1 1 2 1 12 9 1 7 1 1 4 1 1 1 2 1 34 26 8 5 1 3 1 1 2 1 17 5 1 3 1 1 11 10 1 8 1 1 5 1 1 1 1 7 6 5 1 3 1 1 76 70 41 40 2 1 9 4 1 1 1 4 1 1 1 28 2 1 2 1 23 3 1 1 19 3 1 1 8 1 3 1 1 3 1 1 7 1 5 1 3 1 1 28 27 26 14 1 1 11 1 1 1 1 1 1 1 1 1 1 2 1 9 4 1 1 1 4 1 1 1 5 4 3 2 ...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 36ms
memory: 7936kb

input:

1
100000
caabbccaaabcbbbcacbbbbbaabacabcaacacbabbcacacaaccacbbccbabbaccccbaccabcabacbbccccacbabaccacbaaabcccacaccbbaaacbbbcacbccbaaaabaabbaacaaacaaacbaacbcaaacccabcccbbacccccaacbccabbbcaccaaaccbcccbbcbacccaaacbaabaaabaabaccccccbcccccaabcaacbbcbbaacbccabccbbbbabbcbcbcbabcbaaabccccaaabacaaacaaabbabbca...

output:

1 6 5 4 3 1 1 113 15 14 2 1 4 3 2 1 7 1 1 1 1 1 1 69 7 1 2 1 3 2 1 61 5 1 3 1 1 8 3 2 1 2 1 2 1 47 3 1 1 7 1 4 3 1 1 1 15 1 1 6 1 1 1 1 1 3 1 1 3 2 1 21 1 8 1 6 5 1 1 1 1 3 1 1 8 1 3 1 1 3 1 1 28 13 12 4 1 1 1 7 1 5 1 1 1 1 14 13 12 1 4 3 2 1 6 1 3 1 1 1 180 83 10 2 1 7 3 1 1 3 2 1 72 3 2 1 60 9 3 1...

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 43ms
memory: 8160kb

input:

1
100000
hbjlrpypvmluheuxuoquywmrtabyafdpxbvahkvzbqachlachljnappbkfetpkkvazifiswufsuxedthevgdtpljopiqgrtkajrblfflhnmtapnqiwzhphkmimlooxnyltzbskmgybtfgovrduecgarajrvotkaewgedvzaldsxksqyhfajrjdjapnfwgtrwgiraaqafcooyiryhmvtgfspqayywtleaduegvigxpuqmojqbvbdpwficpditskecryzbciajujgrwxglfwpjinrjuwfwsqqwjus...

output:

1 24 10 9 1 2 1 2 1 1 2 1 1 12 2 1 1 5 4 3 1 1 3 2 1 170 2 1 14 1 3 2 1 2 1 7 4 3 2 1 2 1 153 3 2 1 149 5 4 1 2 1 44 1 1 9 1 1 6 1 1 3 2 1 32 1 1 9 4 3 1 1 4 3 2 1 1 19 1 1 3 1 1 13 1 1 1 3 2 1 2 1 4 2 1 1 62 2 1 9 1 7 6 1 4 1 2 1 43 1 2 1 3 2 1 2 1 14 2 1 11 1 9 3 2 1 2 1 3 2 1 18 1 2 1 2 1 12 1 5 ...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 30ms
memory: 8592kb

input:

1
100000
abacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabahabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabagabacabadabacabaeabacabadabacabafabacabadabacabaeabacabadabacabaiabacabadabacabaeabacabadabacabafaba...

output:

65536 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 64 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 128 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1...

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 23ms
memory: 8156kb

input:

1
100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 18ms
memory: 8016kb

input:

1
100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 99969 99968 99967 99966 99965 99964 99963 99962 99961 99960 99959 99958 99957 99956 99955 99954 99953 99952 99951...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 19ms
memory: 8012kb

input:

1
100000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result:

ok 100000 numbers

Extra Test:

score: 0
Extra Test Passed