QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#148686 | #3532. Sequence exploration | OneWan | AC ✓ | 14ms | 22160kb | C++20 | 1.5kb | 2023-08-23 17:29:39 | 2023-08-23 20:26:16 |
Judging History
answer
// Problem: D - Sequence exploration
// Contest: Virtual Judge - Namomo Summer Camp 23 Day 3
// URL: https://vjudge.net/contest/577185#problem/D
// Memory Limit: 254 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
long long n;
int m;
cin >> n >> m;
// int cnt = 1;
vector<int> res;
res.emplace_back(1);
auto get = [&](const vector<int> &res) {
vector<int> temp;
int cnt0 = 0, last = res.front();
for (auto &x : res) {
if (x == last) {
cnt0++;
} else {
temp.emplace_back(cnt0);
temp.emplace_back(last);
cnt0 = 1;
}
last = x;
}
if (cnt0) {
temp.emplace_back(cnt0);
temp.emplace_back(last);
}
return temp;
};
vector<vector<int>> ans(50);
ans[1] = res;
for (int i = 2 ; i < 50 ; i++) {
ans[i] = get(ans[i - 1]);
}
for (int i = 1 ; i < 50 ; i++) {
if (ans[i].size() > m) {
reverse(begin(ans[i]), end(ans[i]));
ans[i].resize(m);
reverse(begin(ans[i]), end(ans[i]));
}
}
if (n <= 50) {
for (int i = max(0, int(ans[n].size()) - m) ; i < int(ans[n].size()) ; i++) {
cout << ans[n][i];
}
} else {
set<vector<int>> st;
int start = -1;
for (int i = 1 ; i < 50 ; i++) {
if (st.count(ans[i])) {
start = i;
break;
}
st.emplace(ans[i]);
}
int z = (n - start) % 4;
for (int i = max(0, int(ans[start + z].size()) - m) ; i < int(ans[start + z].size()) ; i++) {
cout << ans[start + z][i];
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 19712kb
input:
1 2
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 20576kb
input:
42 1
output:
1
result:
ok answer is '1'
Test #3:
score: 0
Accepted
time: 3ms
memory: 20748kb
input:
10 10
output:
3113112211
result:
ok answer is '3113112211'
Test #4:
score: 0
Accepted
time: 3ms
memory: 22112kb
input:
15 10
output:
2113212221
result:
ok answer is '2113212221'
Test #5:
score: 0
Accepted
time: 3ms
memory: 19556kb
input:
18 10
output:
2113112211
result:
ok answer is '2113112211'
Test #6:
score: 0
Accepted
time: 6ms
memory: 18560kb
input:
30 10
output:
2113112211
result:
ok answer is '2113112211'
Test #7:
score: 0
Accepted
time: 0ms
memory: 18464kb
input:
100 16
output:
1322211312113211
result:
ok answer is '1322211312113211'
Test #8:
score: 0
Accepted
time: 10ms
memory: 18076kb
input:
101 16
output:
2113111221131221
result:
ok answer is '2113111221131221'
Test #9:
score: 0
Accepted
time: 3ms
memory: 22024kb
input:
102 16
output:
1331222113112211
result:
ok answer is '1331222113112211'
Test #10:
score: 0
Accepted
time: 11ms
memory: 19496kb
input:
103 16
output:
2311322113212221
result:
ok answer is '2311322113212221'
Test #11:
score: 0
Accepted
time: 2ms
memory: 21064kb
input:
104 16
output:
1322211312113211
result:
ok answer is '1322211312113211'
Test #12:
score: 0
Accepted
time: 0ms
memory: 19436kb
input:
1 1000
output:
1
result:
ok answer is '1'
Test #13:
score: 0
Accepted
time: 2ms
memory: 21156kb
input:
2 1000
output:
11
result:
ok answer is '11'
Test #14:
score: 0
Accepted
time: 3ms
memory: 20600kb
input:
3 1000
output:
21
result:
ok answer is '21'
Test #15:
score: 0
Accepted
time: 11ms
memory: 21660kb
input:
4 1000
output:
1211
result:
ok answer is '1211'
Test #16:
score: 0
Accepted
time: 9ms
memory: 21176kb
input:
5 1000
output:
111221
result:
ok answer is '111221'
Test #17:
score: 0
Accepted
time: 7ms
memory: 18436kb
input:
6 1000
output:
312211
result:
ok answer is '312211'
Test #18:
score: 0
Accepted
time: 3ms
memory: 19572kb
input:
7 1000
output:
13112221
result:
ok answer is '13112221'
Test #19:
score: 0
Accepted
time: 3ms
memory: 20180kb
input:
8 1000
output:
1113213211
result:
ok answer is '1113213211'
Test #20:
score: 0
Accepted
time: 8ms
memory: 20144kb
input:
9 1000
output:
31131211131221
result:
ok answer is '31131211131221'
Test #21:
score: 0
Accepted
time: 4ms
memory: 20060kb
input:
10 1000
output:
13211311123113112211
result:
ok answer is '13211311123113112211'
Test #22:
score: 0
Accepted
time: 13ms
memory: 19100kb
input:
11 1000
output:
11131221133112132113212221
result:
ok answer is '11131221133112132113212221'
Test #23:
score: 0
Accepted
time: 5ms
memory: 20736kb
input:
12 1000
output:
3113112221232112111312211312113211
result:
ok answer is '3113112221232112111312211312113211'
Test #24:
score: 0
Accepted
time: 6ms
memory: 20728kb
input:
13 1000
output:
1321132132111213122112311311222113111221131221
result:
ok answer is '1321132132111213122112311311222113111221131221'
Test #25:
score: 0
Accepted
time: 6ms
memory: 20476kb
input:
14 1000
output:
11131221131211131231121113112221121321132132211331222113112211
result:
ok answer is '11131221131211131231121113112221121321132132211331222113112211'
Test #26:
score: 0
Accepted
time: 1ms
memory: 20688kb
input:
15 1000
output:
311311222113111231131112132112311321322112111312211312111322212311322113212221
result:
ok answer is '311311222113111231131112132112...2211312111322212311322113212221'
Test #27:
score: 0
Accepted
time: 4ms
memory: 20076kb
input:
16 1000
output:
132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211
result:
ok answer is '132113213221133112132113311211...2311332111213211322211312113211'
Test #28:
score: 0
Accepted
time: 7ms
memory: 20144kb
input:
17 1000
output:
11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221
result:
ok answer is '111312211312111322212321121113...1121113122113322113111221131221'
Test #29:
score: 0
Accepted
time: 11ms
memory: 20184kb
input:
18 1000
output:
31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211
result:
ok answer is '311311222113111231133211121312...1131122212322211331222113112211'
Test #30:
score: 0
Accepted
time: 10ms
memory: 22104kb
input:
19 1000
output:
1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221
result:
ok answer is '132113213221133112132123123112...3213211121332212311322113212221'
Test #31:
score: 0
Accepted
time: 0ms
memory: 20768kb
input:
20 1000
output:
11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211
result:
ok answer is '111312211312111322212321121113...2112322111213211322211312113211'
Test #32:
score: 0
Accepted
time: 12ms
memory: 21772kb
input:
21 1000
output:
311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112...
result:
ok answer is '311311222113111231133211121312...1121113122113322113111221131221'
Test #33:
score: 0
Accepted
time: 3ms
memory: 21596kb
input:
22 1000
output:
132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311...
result:
ok answer is '132113213221133112132123123112...1131122212322211331222113112211'
Test #34:
score: 0
Accepted
time: 4ms
memory: 21036kb
input:
23 1000
output:
111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312...
result:
ok answer is '111312211312111322212321121113...3213211121332212311322113212221'
Test #35:
score: 0
Accepted
time: 3ms
memory: 19584kb
input:
24 1000
output:
311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211213211321322113...
result:
ok answer is '311311222113111231133211121312...2112322111213211322211312113211'
Test #36:
score: 0
Accepted
time: 5ms
memory: 19032kb
input:
25 1000
output:
322112111312211312111322111213122112311311123112112322211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211213211321322113311213...
result:
ok answer is '322112111312211312111322111213...1121113122113322113111221131221'
Test #37:
score: 0
Accepted
time: 6ms
memory: 19708kb
input:
26 1000
output:
121113122112132113121113222112311311221112131221123113112211322112211213322112111312211312111322212321121113121112131112132112311321322112111312211312111322211322111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311122113222123122113...
result:
ok answer is '121113122112132113121113222112...1131122212322211331222113112211'
Test #38:
score: 0
Accepted
time: 7ms
memory: 18504kb
input:
27 1000
output:
133122112231131122211211131221131112311332211213211321322113312221133211121311222113321132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221...
result:
ok answer is '133122112231131122211211131221...3213211121332212311322113212221'
Test #39:
score: 0
Accepted
time: 3ms
memory: 19492kb
input:
28 1000
output:
322112311311222113111221221113122112132113121113222112311311222113111231133221121113311211131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211...
result:
ok answer is '322112311311222113111221221113...2112322111213211322211312113211'
Test #40:
score: 0
Accepted
time: 5ms
memory: 19048kb
input:
29 1000
output:
131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111311222112132113311213211221121332211231232112311321322112311311222113311213212322211231131122211311123113223112111311...
result:
ok answer is '131122113221122112133221121321...1121113122113322113111221131221'
Test #41:
score: 0
Accepted
time: 12ms
memory: 21636kb
input:
1000000000 1000
output:
132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112...
result:
ok answer is '132221121311121312211213211312...2112322111213211322211312113211'
Test #42:
score: 0
Accepted
time: 6ms
memory: 18908kb
input:
1000000001 1000
output:
211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113222113223113112221121113311211131122211211131221131211322113321132211221121332211213211321322113311213212312311211131122...
result:
ok answer is '211213211321322113311213211322...1121113122113322113111221131221'
Test #43:
score: 0
Accepted
time: 5ms
memory: 18464kb
input:
1000000002 1000
output:
122113222123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211322132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112...
result:
ok answer is '122113222123122113222122211211...1131122212322211331222113112211'
Test #44:
score: 0
Accepted
time: 3ms
memory: 20516kb
input:
1000000003 1000
output:
112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312...
result:
ok answer is '112221133112132123222112111312...3213211121332212311322113212221'
Test #45:
score: 0
Accepted
time: 3ms
memory: 22160kb
input:
1000000004 1000
output:
132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112...
result:
ok answer is '132221121311121312211213211312...2112322111213211322211312113211'
Test #46:
score: 0
Accepted
time: 6ms
memory: 21128kb
input:
1000000000000000000 1000
output:
132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112...
result:
ok answer is '132221121311121312211213211312...2112322111213211322211312113211'
Test #47:
score: 0
Accepted
time: 14ms
memory: 18992kb
input:
999999999999999999 1000
output:
112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312...
result:
ok answer is '112221133112132123222112111312...3213211121332212311322113212221'
Test #48:
score: 0
Accepted
time: 7ms
memory: 19084kb
input:
999999999999999998 1000
output:
122113222123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221222112112322211322132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112...
result:
ok answer is '122113222123122113222122211211...1131122212322211331222113112211'
Test #49:
score: 0
Accepted
time: 6ms
memory: 19684kb
input:
999999999999999997 1000
output:
211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113222113223113112221121113311211131122211211131221131211322113321132211221121332211213211321322113311213212312311211131122...
result:
ok answer is '211213211321322113311213211322...1121113122113322113111221131221'
Test #50:
score: 0
Accepted
time: 4ms
memory: 21184kb
input:
999999399799998949 857
output:
231232112311311222112111312211312111322211322311311222112111331121113112221121113122113121132211332113221122112133221121321132132211331121321231231121113112221121321133112132112211213322113223113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112...
result:
ok answer is '231232112311311222112111312211...1121113122113322113111221131221'