QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#103656	#6353. Kth Lex Min Min Min Subpalindromes	SEM_PRESSAO_pedroteosousa^#	WA	80ms	19224kb	C++23	2.5kb	2023-05-07 06:34:35	2023-05-07 06:34:38

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-07 06:34:38]
评测

测评结果：WA
用时：80ms
内存：19224kb

查看

[2023-05-07 06:34:35]
提交

answer

#include <bits/stdc++.h>
using namespace std;

long long INF = 1'000'000'000'000'000'001ll;

void solve1(int n, int m, long long k) {
    if (k != 1) {
        cout << -1 << endl;
        return;
    }
    while (n--)
        cout << "1 ";
    cout << endl;
}

void solve2(int n, int m, long long k) {
    vector<string> r[] = {
        {"1 ", "2 "},
        {"1 2 ", "2 1 "},
        {"1 1 2 ", "1 2 1 ", "1 2 2 ", "2 1 1 ", "2 1 2 ", "2 2 1 "},
        {"1 1 2 1 ", "1 1 2 2 ", "1 2 1 1 ", "1 2 1 2 ", "1 2 2 1 ", "2 1 1 2 ", "2 1 2 1 ", "2 1 2 2 ", "2 2 1 1 ", "2 2 1 2 "},
        {"1 1 2 1 2 ", "1 1 2 2 1 ", "1 2 1 1 2 ", "1 2 1 2 2 ", "1 2 2 1 1 ", "1 2 2 1 2 ", "2 1 1 2 1 ", "2 1 1 2 2 ", "2 1 2 1 1 ", "2 1 2 2 1 ", "2 2 1 1 2 ", "2 2 1 2 1 "},
        {"1 1 2 1 2 2 ", "1 1 2 2 1 2 ", "1 2 1 1 2 2 ", "1 2 1 2 2 1 ", "1 2 2 1 1 2 ", "1 2 2 1 2 1 ", "2 1 1 2 1 2 ", "2 1 1 2 2 1 ", "2 1 2 1 1 2 ", "2 1 2 2 1 1 ", "2 2 1 1 2 1 ", "2 2 1 2 1 1 "}
    };
    int g = n >= 6 ? 5 : n - 1;
    if (k > r[g].size()) {
        cout << -1 << endl;
        return;
    }
    string s = r[g][k - 1];
    string resp = "";
    for (int i = 0; i < 2 * n; i++) {
        resp += s[i % s.size()];
    }
    cout << resp << endl;
}

void solve3(int n, long long m, long long k) {
    vector<long long> pot(n);
    pot[0] = 1ll;
    for (int i = 1; i < n; i++) {
        if (pot[i - 1] > (INF * 2ll) / m)
            pot[i] = INF;
        else pot[i] = pot[i - 1] * (m - 2);
    }
    vector<long long> resp;
    int l = m + 1, ll = m + 1;
    for (int i = 0; i < n; i++) {
        long long x;
        if (i == 0) {
            if (pot[n - 2] > (INF * 2ll) / m)
                x = INF;
            else x = (m - 1) * pot[n - 2];
        } else {
            x = pot[n - 1 - i];
        }
        long long r = (k - 1ll) / x;
        k -= r * x;
        //cout << k << endl;
        if (k < 0) {
            cout << -1 << endl;
            return;
        }
        long long d = 0;
        if (r >= min(l, ll))
            r++;
        if (r >= max(l, ll))
            r++;
        swap(l, ll);
        l = r;
        if (r >= m) {
            cout << -1 << endl;
            return;
        }
        resp.push_back(r + 1ll);
    }
    for (auto r: resp)
        cout << r << " ";
    cout << endl;
}

int main() {
    int n, m;
    long long k;
    cin >> n >> m >> k;
    if (m == 1) solve1(n, m, k);
    else if (m == 2) solve2(n, m, k);
    else solve3(n, m, k);
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3340kb

input:

1 1 1

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3328kb

input:

2 2 2

output:

2 1

result:

ok 2 number(s): "2 1"

Test #3:

score: 0

Accepted

time: 2ms

memory: 3380kb

input:

3 3 3

output:

2 1 3

result:

ok 3 number(s): "2 1 3"

Test #4:

score: 0

Accepted

time: 2ms

memory: 3372kb

input:

9 9 8244353

output:

2 4 1 2 6 8 1 2 7

result:

ok 9 numbers

Test #5:

score: 0

Accepted

time: 2ms

memory: 3376kb

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

score: 0

Accepted

time: 2ms

memory: 3416kb

input:

3 1000 994253860

output:

998 244 353

result:

ok 3 number(s): "998 244 353"

Test #7:

score: 0

Accepted

time: 2ms

memory: 3352kb

input:

58 4 864691128455135232

output:

4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4

result:

ok 58 numbers

Test #8:

score: 0

Accepted

time: 1ms

memory: 3336kb

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0

Accepted

time: 74ms

memory: 19224kb

input:

1000000 1000000 1000000000000000000

output:

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...

result:

ok 1000000 numbers

Test #10:

score: 0

Accepted

time: 80ms

memory: 19192kb

input:

1000000 4 1000000000000000000

output:

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...

result:

ok 1000000 numbers

Test #11:

score: 0

Accepted

time: 2ms

memory: 3344kb

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

score: 0

Accepted

time: 2ms

memory: 3388kb

input:

1 2 2

output:

result:

ok 1 number(s): "2"

Test #13:

score: 0

Accepted

time: 2ms

memory: 3436kb

input:

2 2 1

output:

1 2

result:

ok 2 number(s): "1 2"

Test #14:

score: 0

Accepted

time: 2ms

memory: 3420kb

input:

3 2 4

output:

2 1 1

result:

ok 3 number(s): "2 1 1"

Test #15:

score: 0

Accepted

time: 1ms

memory: 3340kb

input:

3 2 7

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0

Accepted

time: 2ms

memory: 3348kb

input:

4 2 10

output:

2 2 1 2

result:

ok 4 number(s): "2 2 1 2"

Test #17:

score: 0

Accepted

time: 2ms

memory: 3352kb

input:

4 2 3

output:

1 2 1 1

result:

ok 4 number(s): "1 2 1 1"

Test #18:

score: 0

Accepted

time: 1ms

memory: 3356kb

input:

5 2 7

output:

2 1 1 2 1

result:

ok 5 number(s): "2 1 1 2 1"

Test #19:

score: 0

Accepted

time: 2ms

memory: 3340kb

input:

5 2 13

output:

-1

result:

ok 1 number(s): "-1"

Test #20:

score: 0

Accepted

time: 0ms

memory: 3388kb

input:

6 2 5

output:

1 2 2 1 1 2

result:

ok 6 numbers

Test #21:

score: 0

Accepted

time: 16ms

memory: 6864kb

input:

1000000 2 3

output:

1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 1 2 1 1 2 2 ...

result:

ok 1000000 numbers

Test #22:

score: 0

Accepted

time: 20ms

memory: 6880kb

input:

1000000 2 5

output:

1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 ...

result:

ok 1000000 numbers

Test #23:

score: 0

Accepted

time: 15ms

memory: 6980kb

input:

1000000 2 7

output:

2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 2 1 1 2 1 2 ...

result:

ok 1000000 numbers

Test #24:

score: 0

Accepted

time: 2ms

memory: 3364kb

input:

1000000 2 1000000000000000000

output:

-1

result:

ok 1 number(s): "-1"

Test #25:

score: -100

Wrong Answer

time: 2ms

memory: 3432kb

input:

1 3 2

output:

result:

wrong answer 1st numbers differ - expected: '2', found: '1'