QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460947#6353. Kth Lex Min Min Min Subpalindromesgrass8cow#WA 50ms15756kbC++171.9kb2024-07-02 14:06:032024-07-02 14:06:04

Judging History

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

  • [2024-07-02 14:06:04]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:15756kb
  • [2024-07-02 14:06:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int a[1010000],oo;
vector<int>vp;
vector<int>brute(int n){
    oo=1e9;
    for(int s=0;s<(1<<n);s++){
		for(int i=1;i<=n;i++)a[i]=((s>>(i-1))&1)+1;
		int an=0;
		for(int i=1;i<=n;i++){
			int d=0;
			while(a[i-d]==a[i+d])d++;
			an+=d;
		}
		for(int i=1;i<n;i++){
			int d=0;
			while(a[i-d]==a[i+1+d])d++;
			an+=d;
		}
		if(an>oo)continue;
		if(oo>an)oo=an,vp.clear();
		vp.push_back(s);
	}
    return vp;
}
#define ll long long
const ll I=1e18+10;
int n,m;ll k,e[1010000];
int main(){
    scanf("%d%d%lld",&n,&m,&k);
    if(m==1){
        if(k>1)puts("-1");
        else{for(int i=1;i<=n;i++)printf("1 ");}
        return 0;
    }
    if(m>=3){
        e[n+1]=1;
        for(int i=n;i;i--){
            int z=m-min(i,3)+1;
            if(e[i+1]<=I/z)e[i]=e[i+1]*z;
            else e[i]=I;
        }
        if(k>e[1]){puts("-1");return 0;}
        for(int i=1;i<=n;i++){
            int z=(k-1)/e[i+1]+1;
            k-=(z-1)*e[i+1];
            if(i==2&&z>=a[i-1])z++;
            if(i>2){
                int x=a[i-2],y=a[i-1];if(x>y)swap(x,y);
                if(z>=x)z++;if(z>=y)z++;
            }
            a[i]=z;
            printf("%d ",a[i]);
        }
        return 0;
    }
    if(n<=5){
        vector<int>aa=brute(n);
        sort(aa.begin(),aa.end());
        if(aa.size()<k){puts("-1");return 0;}
        int e=aa[k-1];
        for(int i=n-1;i>=0;i--)printf("%d ",((e>>i)&1)+1);
        return 0;
    }
    vector<int>aa=brute(5);
    sort(aa.begin(),aa.end());
    if(aa.size()<k){puts("-1");return 0;}
    int e=aa[k-1];
    for(int i=4;i>=0;i--)a[5-i]=((e>>i)&1);
    for(int i=6;i<=n;i++){
        if(a[i-2]==a[i-1])a[i]=a[i-3];
        else if(a[i-1]==a[i-3])a[i]=a[i-4]^1;
        else a[i]=a[i-5]^1;
    }
    for(int i=1;i<=n;i++)printf("%d ",a[i]+1);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1 1

output:

1 

result:

ok 1 number(s): "1"

Test #2:

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

input:

2 2 2

output:

2 1 

result:

ok 2 number(s): "2 1"

Test #3:

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

input:

3 3 3

output:

2 1 3 

result:

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

Test #4:

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

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

input:

10 7 998244353

output:

-1

result:

ok 1 number(s): "-1"

Test #6:

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

input:

3 1000 994253860

output:

998 244 353 

result:

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

Test #7:

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

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

input:

58 4 864691128455135233

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: 0
Accepted
time: 50ms
memory: 15756kb

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: 38ms
memory: 15744kb

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: 1ms
memory: 3600kb

input:

1 1 2

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

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

input:

1 2 2

output:

2 

result:

ok 1 number(s): "2"

Test #13:

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

input:

2 2 1

output:

1 2 

result:

ok 2 number(s): "1 2"

Test #14:

score: -100
Wrong Answer
time: 0ms
memory: 3756kb

input:

3 2 4

output:

2 2 1 

result:

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