QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#102338#6353. Kth Lex Min Min Min SubpalindromesAlpha_Q#WA 83ms11520kbC++172.5kb2023-05-03 04:56:392023-05-03 04:56:42

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-03 04:56:42]
  • 评测
  • 测评结果:WA
  • 用时:83ms
  • 内存:11520kb
  • [2023-05-03 04:56:39]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;
const __int128 INF = 1e18 + 69;

int n, m; long long k, power[N];
vector <int> two[] = {{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 main() {
  cin >> n >> m >> k;
  if (n == 1) {
    if (k > m) puts("-1");
    else printf("%lld\n", k);
    return 0;
  }
  if (m == 1) {
    if (k > 1) {
      puts("-1");
    } else {
      for (int i = 1; i <= n; ++i) printf("1 ");
      puts(""); 
    }
    return 0;
  }
  if (n == 2) {
    long long total = (long long) m * (m - 1);
    if (total < k) {
      puts("-1");
    } else {
      long long A = (k + m - 2) / (m - 1);
      k -= (A - 1) * (m - 1);
      long long B = k;
      if (B >= A) ++B;
      printf("%lld %lld\n", A, B);
    }
    return 0;
  }
  if (m == 2) {
    if (n <= 6) {
      vector <vector <int>> who;
      for (int i = 0; i < 12; ++i) {
        who.emplace_back(two[i].begin(), two[i].begin() + n);
      }
      who.erase(unique(who.begin(), who.end()), who.end());
      if (k > who.size()) {
        puts("-1");
      } else {
        for (int x : who[k - 1]) printf("%d ", x); 
        puts("");
      }
    } else {
      if (k > 12) {
        puts("-1");
      } else {
        for (int i = 0; i < n; ++i) printf("%d ", two[k - 1][i % 6]);
        puts("");
      }
    }
    return 0;
  }
  if (m == 3) {
    if (k > 6) {
      puts("-1");
    } else {
      vector <int> vec({1, 2, 3});
      for (int i = 1; i < k; ++i) next_permutation(vec.begin(), vec.end());
      for (int i = 0; i < n; ++i) printf("%d ", vec[i % 3]);
      puts("");
    }
    return 0;
  }
  power[0] = 1;
  for (int i = 1; i < N; ++i) {
    power[i] = min(INF, (__int128) power[i - 1] * (m - 2)); 
  }
  __int128 total = min(INF, (__int128) power[n - 2] * m * (m - 1));
  if (total < k) {
    puts("-1");
    return 0;
  }
  int last = m + 1, prevLast = m + 1;
  for (int i = 1; i <= n; ++i) {
    __int128 each = i == 1 ? min(INF, (__int128) power[n - 2] * (m - 1)) : power[n - i];
    int cur = (k + each - 1) / each;
    k -= (cur - 1) * each;
    if (last <= cur) ++cur;
    if (prevLast <= cur) ++cur;
    printf("%d ", cur);
    swap(last, prevLast), last = cur;
  }
  puts("");
  return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

score: 0
Accepted
time: 3ms
memory: 11516kb

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

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

score: 0
Accepted
time: 1ms
memory: 11404kb

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

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

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: 2ms
memory: 11228kb

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: -100
Wrong Answer
time: 83ms
memory: 11520kb

input:

1000000 1000000 1000000000000000000

output:

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

result:

wrong answer 3rd numbers differ - expected: '3', found: '2'