Submission #4866

#	Time	Username	Problem	Language	Result	Execution time	Memory
4866		tncks0121	K-th path (IZhO11_kthpath)	C++98	100 / 100	0 ms	1328 KiB

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 (stderr)

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 / 100