QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137118#6353. Kth Lex Min Min Min Subpalindromesberarchegas#WA 47ms26984kbC++175.4kb2023-08-09 21:09:562023-08-09 21:09:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 21:09:58]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:26984kb
  • [2023-08-09 21:09:56]
  • 提交

answer

#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <random>
#include <bits/stdc++.h>

using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down

#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());

const int maxn = 10*100000 + 10;

// const int inf = 1000000000;
// const ll inf = 1000000000000000000LL;

// const ll mod = 998244353;
// const ll mod = 1000000007; // 10^9 + 7

ll n, m, k;

ll pw[maxn];

void printAnswer(vector<ll> v = {})
{
    if( v.empty() )
        cout << -1 << endl;
    else
    {
        for(int x: v)
            cout << x << " ";

        cout << endl;
    }

    exit(0);
}

void dealSmallCases()
{
    if( n == 1 )
    {
        if( k <= m )
            printAnswer( { k } );
        else
            printAnswer();
    }

    if( m == 1 )
    {
        if( k == 1 )
            printAnswer( vector<ll>(1, n) );
        else
            printAnswer();
    }

    if( n == 2 )
    {
        ll num = m*(m - 1);

        if( k <= num )
        {
            ll a = ((k - 1)/(m - 1)) + 1;
            ll b = ((k - 1)%(m - 1)) + 1;
            if( b >= a ) b++;

            printAnswer( { a , b } );
        }
        else
            printAnswer();
    }
}

ll lim;

ll mult(ll a, ll b)
{
    if( a > lim || b > lim || a > lim/b )
        return lim + 1;

    return min( a*b , lim + 1 );
}

void generalCase()
{
    pw[0] = 1;

    for(int i = 1 ; i <= n ; i++)
        pw[i] = mult( pw[i - 1] , m - 2 );

    ll numWays = mult( m , m - 1 );
    numWays = mult( numWays , pw[n - 2] );

    if( numWays < k )
        printAnswer();

    vector<ll> ans(n);

    for(int i = 0 ; i < n ; i++)
    {
        ll numWaysRemain = pw[n - i - 1];
        if( i == 0 ) numWaysRemain = mult( m - 1 , pw[n - 2] );

        ans[i] = (k - 1)/numWaysRemain;
        k -= ans[i]*numWaysRemain;

        ans[i]++;

        ll a = (i >= 1) ? ans[i - 1] : m + 1;
        ll b = (i >= 2) ? ans[i - 2] : m + 1;

        if( ans[i] >= max( a , b ) )
            ans[i] += 2;
        else if( ans[i] >= min( a , b ) && abs(a - b) == 1 )
            ans[i] += 2;
        else if( ans[i] >= min( a , b ) )
            ans[i]++;
    }

    printAnswer(ans);
}

bool isPalindrome(vector<ll> v)
{
    vector<ll> a = v;
    reverse( a.begin() , a.end() );

    return (v == a);
}

int numPalindromes(vector<ll> v)
{
    int ans = 0;
    int n = (int)v.size();

    for(int i = 0 ; i < n ; i++)
    {
        vector<ll> cur = { v[i] };

        for(int j = i + 1 ; j < n ; j++)
        {
            cur.push_back( v[j] );

            if( isPalindrome(cur) )
                ans++;
        }
    }

    return ans;
}

void binaryArray()
{
    if( n < 6 )
    {
        int minValue = 738242;
        vector< vector<ll> > answers;

        for(int mask = 0 ; mask < (1 << n) ; mask++)
        {
            vector<ll> cur(n);

            for(int j = 0 ; j < n ; j++)
                cur[j] = (mask >> j)%2;

            minValue = min( minValue , numPalindromes(cur) );
        }

        for(int mask = 0 ; mask < (1 << n) ; mask++)
        {
            vector<ll> cur(n);

            for(int j = 0 ; j < n ; j++)
                cur[j] = (mask >> j)%2;

            for(int j = 0 ; j < n ; j++)
                cur[j]++;

            if( numPalindromes(cur) == minValue )
                answers.push_back( cur );
        }

        if( k <= (int)answers.size() )
            printAnswer( answers[k - 1] );
        else
            printAnswer();
    }

    vector< vector<ll> > starts = {
        {1, 1, 0, 1, 0, 0},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 0, 1, 0},
        {0, 1, 1, 0, 1, 0},
        {1, 0, 0, 1, 1, 0},
        {0, 1, 0, 1, 1, 0},
        {1, 0, 1, 0, 0, 1},
        {0, 1, 1, 0, 0, 1},
        {1, 0, 0, 1, 0, 1},
        {0, 0, 1, 1, 0, 1},
        {0, 1, 0, 0, 1, 1},
        {0, 0, 1, 0, 1, 1},
    };

    sort( starts.begin() , starts.end() );

    if( k <= 12 )
    {
        vector<ll> ans = starts[k - 1];

        for(int i = 6 ; i < n ; i++)
            ans.push_back( ans[i%6] );

        for(int i = 0 ; i < n ; i++)
            ans[i]++;

        printAnswer(ans);
    }
    else
        printAnswer();
}

void solve(int testcase)
{
    cin >> n >> m >> k;
    lim = k;

    dealSmallCases();

    if( m >= 3 )
        generalCase();
    else
        binaryArray();
}

int main()
{
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);

    int t = 1;
    // cin >> t;

    for(int testcase = 1 ; testcase <= t ; testcase++)
        solve( testcase );
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3540kb

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

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

input:

9 9 8244353

output:

2 4 1 2 6 8 1 2 7 

result:

ok 9 numbers

Test #5:

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

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

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

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

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

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

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 47ms
memory: 26940kb

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: -100
Wrong Answer
time: 45ms
memory: 26984kb

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:

wrong answer 999941st numbers differ - expected: '4', found: '3'