Submission #4875

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

kthpath

#include<stdio.h>
#include<algorithm>
using namespace std;
char p[33][33], ch;
int n, m, h, t;
long long C[61][61], D[33][33], T, K, S;
struct point{
	int x, y;
	bool operator <(const point &q)const{
		return p[x][y] < p[q.x][q.y];
	}
}Q[910];
int main()
{
	int i, j, t2, x, y;
	C[0][0] = 1;
	for (i = 1; i <= 60; i++){
		C[i][0] = 1;
		for (j = 1; j <= 60; j++)C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
	}
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++){
		scanf("%s", p[i] + 1);
	}
	Q[t].x = 1, Q[t++].y = 1, D[1][1] = 1;
	scanf("%lld", &K);
	while (1){
		printf("%c", p[Q[h].x][Q[h].y]);
		if (Q[h].x == n&&Q[h].y == m)break;
		t2 = t;
		while (h < t2){
			x = Q[h].x, y = Q[h].y;
			if (x < n){
				if (!D[x + 1][y])Q[t].x = x + 1, Q[t++].y = y;
				D[x + 1][y] += D[x][y];
			}
			if (y < m){
				if (!D[x][y + 1])Q[t].x = x, Q[t++].y = y + 1;
				D[x][y + 1] += D[x][y];
			}
			h++;
		}
		sort(Q + h, Q + t);
		T = 0;
		for (i = h; i < t; i++){
			if (i != h && p[Q[i].x][Q[i].y] != p[Q[i - 1].x][Q[i - 1].y])K -= T, T = 0;
			T += D[Q[i].x][Q[i].y] * C[n - Q[i].x + m - Q[i].y][n - Q[i].x];
			if (T >= K)break;
		}
		ch = p[Q[i].x][Q[i].y];
		for (i = h; i < t; i++){
			if (p[Q[i].x][Q[i].y] == ch)h = i, ch = 0;
			if (!ch && p[Q[i].x][Q[i].y] != p[Q[h].x][Q[h].y])break;
		}
		t = i;
	}
	return 0;
}

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:21: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:23:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", p[i] + 1);
                        ^
kthpath.cpp:26: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