QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #203234 | #6353. Kth Lex Min Min Min Subpalindromes | qzzyq | WA | 39ms | 12160kb | C++14 | 2.4kb | 2023-10-06 16:16:55 | 2023-10-06 16:16:56 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
int n,m,k;
int ans[maxn],pw[maxn];
void print(int id,int res) {
int i;
gdb(id,res,ans[id-1]);
for (i=id;i<=n;i++) {
gdb(i,res,pw[i]);
int nums=(res+pw[i]-1)/pw[i],t=nums;
if (i>=2&&t>=min(ans[i-1],ans[i-2])) t++;
if (i>=3&&t>=max(ans[i-1],ans[i-2])) t++;
ans[i]=t;
res=res-(nums-1)*pw[i];
}
for (i=1;i<=n;i++) printf("%lld ",ans[i]);
exit(0);
}
signed main(void){
int i;
read(n);read(m);read(k);
if (m==1) {
if (k>1) puts("-1");
else {
for (i=1;i<=n;i++) printf("%d ",1);
}
return 0;
}
if (m==2&&n==3) {
if (k==1) puts("1 1 2");
else if (k==2) puts("1 2 1");
else if (k==3) puts("1 2 2");
else if (k==4) puts("2 1 1");
else if (k==5) puts("2 1 2");
else if (k==6) puts("2 2 1");
else puts("-1");
return 0;
}
if (m==2) {
if (k>2) puts("-1");
else if (k==1){
for (i=1;i<=n;i++)
if (i&1) printf("1 ");
else printf("2 ");
}
else {
for (i=1;i<=n;i++)
if (i&1) printf("2 ");
else printf("1 ");
}
return 0;
}
int res=1;
ans[0]=1e9;
for (i=1;i<=n;i++) ans[i]=(i-1)%3+1;
for (i=n;i>=1;i--) {
int tmp=m-2+(i<=2)+(i<=1);
pw[i]=res;
if ((long double)tmp*res>=k) {
int nums=(k+res-1)/res,t=nums;
gdb(i,nums);
if (i>=2&&t>=min(ans[i-1],ans[i-2])) t++;
if (i>=3&&t>=max(ans[i-1],ans[i-2])) t++;
ans[i]=t;
print(i+1,k-(nums-1)*res);
}
else res=res*tmp;
}
puts("-1");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3976kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5844kb
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: 5712kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5916kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5928kb
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: 5584kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 35ms
memory: 12160kb
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: 39ms
memory: 12128kb
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: 0ms
memory: 3592kb
input:
1 1 2
output:
-1
result:
ok 1 number(s): "-1"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
1 2 2
output:
2
result:
ok 1 number(s): "2"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
2 2 1
output:
1 2
result:
ok 2 number(s): "1 2"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
3 2 4
output:
2 1 1
result:
ok 3 number(s): "2 1 1"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
3 2 7
output:
-1
result:
ok 1 number(s): "-1"
Test #16:
score: -100
Wrong Answer
time: 0ms
memory: 3680kb
input:
4 2 10
output:
-1
result:
wrong answer 1st numbers differ - expected: '2', found: '-1'