QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103595#6353. Kth Lex Min Min Min Subpalindromesgapinho#WA 151ms239068kbC++143.3kb2023-05-07 00:10:472023-05-07 00:10:49

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 00:10:49]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:239068kb
  • [2023-05-07 00:10:47]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int ms = 1e6 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;

int fat[ms], ifat[ms];

int fexp(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int c(int a, int b) {
    if(b > a) {
        return 0;
    }
    return fat[a] * ifat[a - b] % mod * ifat[b] % mod;
}
int n, m, k;
int szz;

int cnt(string s) {
    int ans = 0;
    for(int i = 0; i < szz; i++) {
        for(int j = i+1; j < szz; j++) {
            string k = s.substr(i, j-i+1);
            int sz = k.size();
            int isp = 1;
            for(int a = 0; a < sz; a++) {
                if(k[a] != k[sz-a-1]) isp = 0;
            }
            if(isp) ans++;
        }
    }
    return ans;
}

vector<vector<int>> pos;

void rec(string &now) {
    if(now.size() == szz) {
        int x = cnt(now);
        if(x == szz - 2) {
            vector<int> cur;
            for(int i = 0; i < szz; i++) {
                cur.push_back(now[i] - '0' + 1);
            }
            pos.push_back(cur);
        }
        return;
    }
    for(char i = '0'; i <= '1'; ++i) {
        now.push_back(i);
        rec(now);
        now.pop_back();
    }
}

int pot[ms];

vector<int> ans;

void solve(int p, int k, vector<int> proibido) {
    if(p == n) {
        for(auto v : ans) {
            cout << v << ' ';
        }
        cout << endl;
        exit(0);
    }
    __int128_t sum;
    if(p == 0) {
        sum = (m - 1);
        if(n - p - 2 >= 0) {
            sum *= pot[n - p - 2];
        } else {
            sum = 1;
        }
    } else {
        sum = pot[n - p - 1];
    }
    int z = k / sum;

    int hlp = 0;
    vector<int> gamb = proibido;
    sort(gamb.begin(), gamb.end());
    // cout << "quero: " << z << endl;
    // cout << "proibidos: ";
    for(auto x : gamb) {
        if(x <= z + 1) {
            z++;
        }
    }
    // cout << "usando " << z << endl;
    if(z >= m) {
        cout << -1 << endl;
        exit(0);
    }
    ans.push_back(z + 1);
    if(proibido.size() == 2) {
        swap(proibido[0], proibido[1]);
        proibido.pop_back();
    }
    proibido.push_back(z + 1);
    solve(p + 1, k % sum, proibido);
}

int32_t main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> n >> m >> k;
    // cin >> n;
    pot[0] = 1;
    for(int i = 1; i <= n; ++i) {
        __int128_t hlp = pot[i - 1];
        hlp *= (m - 2);
        if(hlp >= inf) {
            hlp = inf;
        }
        pot[i] = hlp;
    }
    string s;
    if(m == 1) {
        if(k == 1) {
            for(int i = 0; i < n; ++i) {
                cout << 1 << ' ';
            }
            cout << endl;
        } else {
            cout << -1 << endl;
        }
        return 0;
    }
    if(m == 2) {
        szz = min(n, 6ll);
        string s;
        rec(s);
        if(k > pos.size()) {
            cout << -1 << endl;
            return 0;
        }
        for(int j = 0; j < n; ++j) {
            cout << pos[k - 1][j % pos[k - 1].size()] << ' ';
        }
        cout << endl;
        return 0;
    }

    solve(0, k-1, {});
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5396kb

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 2ms
memory: 5484kb

input:

2 2 2

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #3:

score: 0
Accepted
time: 2ms
memory: 5400kb

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

score: 0
Accepted
time: 2ms
memory: 5412kb

input:

9 9 8244353

output:

2 4 1 2 6 8 1 2 7 

result:

ok 9 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 5480kb

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

score: 0
Accepted
time: 2ms
memory: 5408kb

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

score: 0
Accepted
time: 2ms
memory: 5504kb

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: 0ms
memory: 5492kb

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 151ms
memory: 239068kb

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: 143ms
memory: 238688kb

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: 5380kb

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

score: -100
Wrong Answer
time: 2ms
memory: 5496kb

input:

1 2 2

output:

-1

result:

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