Submission #4866

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4866	2014-01-05T19:12:35 Z	tncks0121	K-th path (IZhO11_kthpath)	C++	100 / 100	0 ms	1328 KB

kthpath

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

int N, M;
char D[50][50];
ll K;

const int SZ = 100;
int tmp[SZ+2];
struct bigint {
	int digit[SZ+2];

	bigint() { memset(digit, 0, sizeof digit); }
	bigint(int x) { for(int p=0; p<SZ; p++) digit[p] = x%26, x /= 26; }

	void add (const bigint t) {
		for(int i = 0; i < SZ; i++) {
			digit[i] += t.digit[i];
			if(digit[i] >= 26) {
				digit[i+1] += digit[i] / 26;
				digit[i] %= 26;
			}
		}
	}

	void sub (const bigint t) {
		for(int i = 0; i < SZ; i++) {
			digit[i] -= t.digit[i];
			if(digit[i] < 0) --digit[i+1], digit[i] += 26;
		}
	}

	void mul (const bigint t) {
		for(int i = 0; i < SZ; i++) tmp[i] = digit[i], digit[i] = 0;
		for(int i = 0; i < SZ; i++) for(int j = 0; j < SZ-i; j++) {
			digit[i+j] += tmp[i] * t.digit[j];
			digit[i+j+1] += digit[i+j] / 26;
			digit[i+j] %= 26;
		}
	}
};

bigint pow2[300];
char S[100];
ll Table[35][35];
ll C[100][100];

int main() {
	int i, j, k;
	
	scanf("%d%d", &N, &M);
	for(i = 0; i < N; i++) scanf("%s", D[i]);
	scanf("%lld", &K);
	
	if(N == 1 && M == 1) return 0 & putchar(D[0][0]);

	C[0][0] = C[1][0] = C[1][1] = 1;
	for(i = 2; i < 100; i++) {
		C[i][0] = C[i][i] = 1;
		for(j = 1; j < i; j++) C[i][j] = min(C[i-1][j-1] + C[i-1][j], K+1);
	}

	pow2[0].digit[0] = 1;
	for(i = 1; i < 300; i++) {
		pow2[i] = pow2[i-1];
		pow2[i].add(pow2[i-1]);
	}

	bigint low, ret;
	for(k = 298; k >= 0; k--) {
		bigint now = ret;
		now.add(pow2[k]);
		for(i = 0, j = N+M-2; i < N+M-1; i++, j--) S[i] = now.digit[j] + 'a';

		bool pass = false;
		for(i = N+M-1; i < SZ; i++) if(now.digit[i] != 0) pass = true;
		if(pass) continue;

		if(D[0][0] > S[0]) ret = now, pass = true;
		else if(D[0][0] < S[0]) pass = true;
		if(pass) continue;

		memset(Table, 0, sizeof Table);

		if(D[0][0] == S[0]) Table[0][0] = 1;
		for(i = 1; i < N; i++) if(D[i][0] == S[i]) Table[i][0] = Table[i-1][0];
		for(j = 1; j < M; j++) if(D[0][j] == S[j]) Table[0][j] = Table[0][j-1];
		for(i = 1; i < N; i++) for(j = 1; j < M; j++) {
			if(D[i][j] == S[i+j]) Table[i][j] = min(Table[i-1][j] + Table[i][j-1], K+1);
		}

		ll cnt = Table[N-1][M-1];
		bool bigger = (cnt > K);
		for(i = 0; i < N && !bigger; i++) for(j = 0; j < M && !bigger; j++) {
			if((i > 0 || j > 0) && D[i][j] < S[i+j]) {
				ll v = (i>0 ? Table[i-1][j] : 0) + (j>0 ? Table[i][j-1] : 0);
				if(v != 0) {
					int x = N-i-1, y = M-j-1;
					if(C[x+y][x] > K / v) bigger = true;
					else if(K - cnt < C[x+y][x] * v) bigger = true;
					if(!bigger) cnt += C[x+y][x] * v;
				}
			}
		}

		if(!bigger && cnt < K) {
			ret = now;
		}
	}

	ret.add(bigint(1));
	for(i = 0, j = N+M-2; i < N+M-1; i++, j--) S[i] = ret.digit[j] + 'a';
	puts(S);
	return 0;
}

Compilation message

kthpath.cpp: In function 'int main()':
kthpath.cpp:78:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
kthpath.cpp:79:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i = 0; i < N; i++) scanf("%s", D[i]);
                                          ^
kthpath.cpp:80:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &K);
                   ^

Subtask #1
100.0 / 100.0

#	Verdict	Memory	Grader output
1	Correct	1328 KB	Output is correct
2	Correct	1328 KB	Output is correct
3	Correct	1328 KB	Output is correct
4	Correct	1328 KB	Output is correct
5	Correct	1328 KB	Output is correct
6	Correct	1328 KB	Output is correct
7	Correct	1328 KB	Output is correct
8	Correct	1328 KB	Output is correct
9	Correct	1328 KB	Output is correct
10	Correct	1328 KB	Output is correct
11	Correct	1328 KB	Output is correct
12	Correct	1328 KB	Output is correct
13	Correct	1328 KB	Output is correct
14	Correct	1328 KB	Output is correct
15	Correct	1328 KB	Output is correct
16	Correct	1328 KB	Output is correct
17	Correct	1328 KB	Output is correct
18	Correct	1328 KB	Output is correct
19	Correct	1328 KB	Output is correct
20	Correct	1328 KB	Output is correct

Submission #4866

Compilation message

Subtask #1 100.0 / 100.0

Subtask #1
100.0 / 100.0