fork download
copy 
  1. #include<stdio.h>
  2.  
  3. #define ll long long
  4. #define N 1000006
  5.  
  6. ll n, k, res = 0;
  7. ll f[N][3];
  8. int cur[N];
  9.  
  10.  
  11. ll solve(int i, int c) {
  12.     if(i == n) {
  13.         res++;
  14.         cur[i] = c;
  15.         if(res == k) {
  16.             for(int j = 1; j <= n; j++)
  17.                 printf("%d ", cur[j]);
  18.         }
  19.         return 1;
  20.     }
  21.  
  22.     if(f[i][c] != -1 && (res + f[i][c] < k || res >= k)) {
  23.         res += f[i][c];
  24.         if(res > k)
  25.             res = k + 1;
  26.         return f[i][c];
  27.     }
  28.  
  29.     f[i][c] = 0;
  30.     cur[i] = c;
  31.     if(i % 2 == 1)
  32.         if(!c) {
  33.             f[i][c] += solve(i + 1, 1);
  34.             f[i][c] += solve(i + 1, 2);
  35.         }
  36.         else if(c == 1) 
  37.             f[i][c] += solve(i + 1, 0);
  38.         else 
  39.             f[i][c] += solve(i + 1, 1);
  40.     else 
  41.         if(!c)
  42.             f[i][c] += solve(i + 1, 1);
  43.         else if(c == 1) {
  44.             f[i][c] += solve(i + 1, 0);
  45.             f[i][c] += solve(i + 1, 2);
  46.  
  47.         }
  48.         else 
  49.             f[i][c] += solve(i + 1, 0);
  50.     if(f[i][c] > k) 
  51.         f[i][c] = k + 1;
  52.     return f[i][c];
  53. }
  54.  
  55. int main() {
  56.  
  57.     scanf("%lld%lld", &n, &k);
  58.  
  59.     for(int i = 1; i <= n; i++)
  60.         for(int j = 0; j <= 2; j++)
  61.             f[i][j] = -1;
  62.  
  63.     int ans = 0;
  64.     for(int i = 0; i <= 2; i++) 
  65.         ans += solve(1, i);
  66.  
  67.     // printf("%d", res);
  68.  
  69.     if(res < k)
  70.         printf("INFINITY");
  71. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 3
stdout
copy 
0 1 2 1
https://ideone.com/9hqREy
language:
C (gcc 8.3)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!