oj.uz

Submission #810293

# Submission time Handle Problem Language Result Execution time Memory
810293 2023-08-06T08:05:20 Z QwertyPi Costinland (info1cup19_costinland) C++14
20 / 100
 10 ms 4264 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
char c[501][501];
 
void defa(int n, int m){
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if((i == n - 1) == (j == m - 1)) c[i][j] = '.';
			else if(i == n - 1) c[i][j] = 'r';
			else c[i][j] = 'd';
		}
	}
}
 
void pr(int n, int m){
	cout << n << ' ' << m << endl;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << c[i][j];
		}
		cout << endl;
	}
}
 
void part1(int K){
	int n = 0, m = 0;
	if(K <= 5){
		n = 2; m = 5;
		defa(n, m);
		for(int i = 0; i < K - 1; i++){
			c[0][i] = 'X';
		}
		pr(n, m);
	}else if(K <= 8){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = 'X';
		}
		for(int i = 0; i < K - 4; i++){
			c[i][0] = 'X';
		}
		pr(n, m);
	}else if(K <= 10){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = 'X';
		}
		for(int i = 0; i < K - 6; i++){
			c[i][0] = 'X';
		}
		c[1][1] = 'X';
		pr(n, m);
	}else if(K <= 12){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = 'X';
		}
		for(int i = 0; i < K - 8; i++){
			c[i][0] = 'X';
		}
		c[1][1] = 'X';
		c[2][2] = 'X';
		pr(n, m);
	}else if(K <= 16){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 3; i++){
			c[0][i] = c[1][i] = 'X';
		}
		K -= 10;
		if(K){
			c[2][min(3LL, K) - 1] = 'X';
			K -= min(3LL, K);
		}
		if(K){
			c[3][min(3LL, K) - 1] = 'X';
			K -= min(3LL, K);
		}
		pr(n, m);
	}else if(K <= 19){
		n = 5; m = 5;
		defa(n, m);
		for(int i = 0; i < 4; i++){
			c[0][i] = c[1][i] = 'X';
		}
		K -= 15;
		if(K){
			c[2][min(4LL, K) - 1] = 'X';
			K -= min(4LL, K);
		}
		if(K){
			c[3][min(4LL, K) - 1] = 'X';
			K -= min(4LL, K);
		}
		pr(n, m);
	}
}
 
__int128_t C[501][501];
 
bool part2(int K){
	int N = 56, M = 56;
	defa(N, M);
	if(K <= M){
		for(int i = 0; i < K - 1; i++){
			c[0][i] = 'X';
		}
		pr(N, M);
		return true;
	}
	int _K = K;
	for(int m = M; m >= 1; m--){
		defa(N, M);
		for(int l = 1; l <= M + 1; l++){
            for(int r = 0; r < 100000; r++){
                K = _K;
                if(K <= C[m - 1][l + 1]){
                    K -= C[m - 1][l];
                    for(int j = 0; j < l - 1; j++){
                        for(int i = 0; i <= m - 2; i++){
                            c[j][i] = 'X';
                        }
                    }
                    for(int i = 0; i <= m - 2; i++){
                        c[l - 1][i] = rng() % 2 ? 'X' : '.';
                    }
                    for(int j = l; j < N - 1; j++){
                        for(int k = m - 2; k >= 0; k--){
                            if(K >= C[k][l - 1]){
                                K -= C[k][l - 1];
                                c[j][k] = 'X';
                                break;
                            }
                        }
                    }
                    if(K == 0) { pr(N, M); return true; }
                    break;
                }
            }
		}
	}
	return false;
}
 
int32_t main(){
	for(int i = 0; i <= 500; i++){
		C[i][0] = C[0][i] = 1;
	}
	for(int i = 1; i <= 500; i++){
		for(int j = 1; j <= 500; j++){
			C[i][j] = C[i - 1][j] + C[i][j - 1];
		}
	}
	int K; cin >> K;
	if(K <= 19){
		part1(K);
	}else{
		part2(K);
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Correct! Your size: 5
2 Correct 2 ms 4180 KB Correct! Your size: 5
3 Correct 2 ms 4180 KB Correct! Your size: 5
4 Correct 3 ms 4180 KB Correct! Your size: 5
5 Correct 3 ms 4240 KB Correct! Your size: 5
6 Correct 2 ms 4232 KB Correct! Your size: 5
7 Correct 3 ms 4180 KB Correct! Your size: 5
8 Correct 3 ms 4232 KB Correct! Your size: 5
9 Correct 2 ms 4180 KB Correct! Your size: 5

Subtask #2
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 4264 KB The matrix does not generate the required number of Costins
2 Halted 0 ms 0 KB -