QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#148686#3532. Sequence explorationOneWanAC ✓14ms22160kbC++201.5kb2023-08-23 17:29:392023-08-23 20:26:16

Judging History

This is the latest submission verdict.

  • [2023-08-23 20:26:16]
  • Judged
  • Verdict: AC
  • Time: 14ms
  • Memory: 22160kb
  • [2023-08-23 17:29:39]
  • Submitted

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'