oj.uz

Submission #810392

# Submission time Handle Problem Language Result Execution time Memory
810392 2023-08-06T09:07:29 Z QwertyPi Costinland (info1cup19_costinland) C++14
100 / 100
 80 ms 420 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];
 
int n, m;
void init(){
	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 output(){
	cout << n << ' ' << m << endl;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << c[i][j];
		}
		cout << endl;
	}
}

ostream& operator<< (ostream& out, __int128_t x){
    string s; while(x > 0) s.push_back('0' + (x % 10)), x /= 10; reverse(s.begin(), s.end());
    return out << s;
}
 
__int128_t dp[50][50][2];
__int128_t C[501][501];

void revert(int i, int j){
    if(c[i][j] == 'X'){
        dp[i][j + 1][0] -= dp[i][j][0] + dp[i][j][1];
        dp[i + 1][j][1] -= dp[i][j][0] + dp[i][j][1];
    }else if(c[i][j] == 'r'){
        dp[i][j + 1][0] -= dp[i][j][0] + dp[i][j][1];
    }else if(c[i][j] == 'd'){
        dp[i + 1][j][1] -= dp[i][j][0] + dp[i][j][1];
    }else{
        if(j + 1 < m) dp[i][j + 1][0] -= dp[i][j][0];
        if(i + 1 < n) dp[i + 1][j][1] -= dp[i][j][1];
    }
}

void update(int i, int j){
    if(c[i][j] == 'X'){
        dp[i][j + 1][0] += dp[i][j][0] + dp[i][j][1];
        dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1];
    }else if(c[i][j] == 'r'){
        dp[i][j + 1][0] += dp[i][j][0] + dp[i][j][1];
    }else if(c[i][j] == 'd'){
        dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1];
    }else{
        if(j + 1 < m) dp[i][j + 1][0] += dp[i][j][0];
        if(i + 1 < n) dp[i + 1][j][1] += dp[i][j][1];
    }
}

__int128_t get(int i, int j){
    return dp[i][j][0] + dp[i][j][1];
}

__int128_t calc(){
    int N = n, M = m;
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1; dp[0][0][1] = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            update(i, j);
        }
    }
    return dp[N - 1][M - 1][0] + dp[N - 1][M - 1][1];
}

void part1(int K){
	if(K <= 5){
		n = 2; m = 5;
		init();
		for(int i = 0; i < K - 1; i++){
			c[0][i] = 'X';
		}
		output();
	}else if(K <= 8){
		n = 5; m = 5;
		init();
		for(int i = 0; i < 4; i++){
			c[0][i] = 'X';
		}
		for(int i = 0; i < K - 4; i++){
			c[i][0] = 'X';
		}
		output();
	}else if(K <= 10){
		n = 5; m = 5;
		init();
		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';
		output();
	}else if(K <= 12){
		n = 5; m = 5;
		init();
		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';
		output();
	}else if(K <= 16){
		n = 5; m = 5;
		init();
		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);
		}
		output();
	}else if(K <= 19){
		n = 5; m = 5;
		init();
		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);
		}
		output();
	}
}

void part2(int K){
	n = m = 49;
    if(K <= m){
        n = 2, m = K;
        init();
		for(int i = 0; i < K - 1; i++){
			c[0][i] = 'X';
		}
		output();
		return;
	}
    for(int L = 1; L <= 26; L++){
        for(int round = 0; round < 10000; round++){
            init();
            for(int i = 0; i < L; i++){
                for(int j = 0; j < m - 1; j++){
                    c[i][j] = rng() % 10 ? 'X' : '.';
                }
            }
            __int128_t cur = calc(); if(cur > K) continue;
            for(int i = L; i < n - 1; i++){
                for(int j = m - 2; j >= 0; j--){
                    c[i][j] = 'X';
                    __int128_t nxt = calc();
                    if(nxt > K) c[i][j] = '.';
                    else cur = nxt;
                }
            }
            if(calc() == K){
                output();
                return;
            }
        }
    }
}
 
int32_t main(){
	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 0 ms 212 KB Correct! Your size: 5
2 Correct 0 ms 212 KB Correct! Your size: 5
3 Correct 0 ms 212 KB Correct! Your size: 5
4 Correct 0 ms 212 KB Correct! Your size: 5
5 Correct 0 ms 212 KB Correct! Your size: 5
6 Correct 0 ms 212 KB Correct! Your size: 5
7 Correct 0 ms 212 KB Correct! Your size: 5
8 Correct 0 ms 212 KB Correct! Your size: 5
9 Correct 0 ms 212 KB Correct! Your size: 5

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 416 KB Correct! Your size: 49
2 Correct 28 ms 412 KB Correct! Your size: 49
3 Correct 28 ms 420 KB Correct! Your size: 49
4 Correct 34 ms 400 KB Correct! Your size: 49
5 Correct 54 ms 340 KB Correct! Your size: 49
6 Correct 80 ms 340 KB Correct! Your size: 49
7 Correct 30 ms 396 KB Correct! Your size: 49
8 Correct 80 ms 396 KB Correct! Your size: 49