Submission #1195357
Source Code Expand
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <numeric>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...) 42
#endif
typedef long long int int64;
const long long INF = (long long) 1e18;
const int N = 105;
long long dpl[N][N];
long long dpr[N][N];
void sadd(long long &a, long long b)
{
a += b;
if (a >= INF) a = INF;
}
long long count(vector <int> &lh, vector <int> &rh)
{
/* for (int x : lh)
eprintf("%d ", x);
eprintf("\n");
for (int x : rh)
eprintf("%d ", x);
eprintf("\n");
*/ memset(dpl, 0, sizeof dpl);
memset(dpr, 0, sizeof dpr);
dpl[0][0] = 1;
for (int i = 0; i <= (int) lh.size(); i++)
for (int j = 0; j <= (int) rh.size(); j++)
{
// eprintf("%d, %d : %lld\n", i, j, dp[i][j] );
sadd(dpr[i][j], dpl[i][j] );
if (i != (int) lh.size() ) sadd(dpl[i + 1][j], dpl[i][j] );
if (j != (int) rh.size() ) sadd(dpr[i][j + 1], dpr[i][j] );
if (i != (int) lh.size() && j != (int) rh.size() && lh[i] == rh[j] )
sadd(dpl[i + 1][j + 1], dpr[i][j] );
}
// eprintf("\n\n");
return dpr[(int) lh.size()][(int) rh.size() ] - 1;
}
vector <int> lh, rh;
int main(int, char **)
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
long long X;
scanf("%lld", &X);
int cur = 1;
while (count(lh, rh) != X)
{
lh.insert(lh.begin(), cur);
for (int i = 0; i <= (int) rh.size(); i++)
{
vector <int> nrh = rh;
nrh.insert(nrh.begin() + i, cur);
if (count(lh, nrh) <= X)
{
rh = nrh;
break;
}
}
cur++;
}
printf("%d\n", (int) lh.size() + (int) rh.size() );
for (int x : lh)
printf("%d ", x);
for (int x : rh)
printf("%d ", x);
return 0;
}
Submission Info
Submission Time
2017-04-01 21:29:40+0900
Task
C - Tautonym Puzzle
User
Merkurev
Language
C++14 (GCC 5.4.1)
Score
1000
Code Size
1957 Byte
Status
AC
Exec Time
37 ms
Memory
384 KB
Compile Error
./Main.cpp: In function ‘int main(int, char**)’:
./Main.cpp:70:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &X);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1000 / 1000
Status
Set Name
Test Cases
Sample
00_example_01.txt, 00_example_02.txt
All
00_example_01.txt, 00_example_02.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt
Case Name
Status
Exec Time
Memory
00_example_01.txt
AC
1 ms
384 KB
00_example_02.txt
AC
2 ms
384 KB
01.txt
AC
13 ms
384 KB
02.txt
AC
2 ms
384 KB
03.txt
AC
2 ms
384 KB
04.txt
AC
8 ms
384 KB
05.txt
AC
2 ms
384 KB
06.txt
AC
2 ms
384 KB
07.txt
AC
7 ms
384 KB
08.txt
AC
10 ms
384 KB
09.txt
AC
2 ms
384 KB
10.txt
AC
2 ms
384 KB
11.txt
AC
4 ms
384 KB
12.txt
AC
2 ms
384 KB
13.txt
AC
6 ms
384 KB
14.txt
AC
3 ms
384 KB
15.txt
AC
5 ms
384 KB
16.txt
AC
2 ms
384 KB
17.txt
AC
1 ms
384 KB
18.txt
AC
3 ms
384 KB
19.txt
AC
6 ms
384 KB
20.txt
AC
3 ms
384 KB
21.txt
AC
8 ms
384 KB
22.txt
AC
2 ms
384 KB
23.txt
AC
10 ms
384 KB
24.txt
AC
4 ms
384 KB
25.txt
AC
2 ms
384 KB
26.txt
AC
8 ms
384 KB
27.txt
AC
37 ms
384 KB
28.txt
AC
1 ms
384 KB
29.txt
AC
18 ms
384 KB
30.txt
AC
12 ms
384 KB