oj.uz

Submission #810360

# Submission time Handle Problem Language Result Execution time Memory
810360 2023-08-06T08:46:52 Z QwertyPi Costinland (info1cup19_costinland) C++14
0 / 100
 500 ms 8180 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[501][501][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 part2(int K){
	n = m = 49;
    for(int L = 1; L <= 26; L++){
        for(int round = 0; round < 100; round++){
            init();
            for(int i = 0; i < L; i++){
                for(int j = 0; j < m - 1; j++){
                    c[i][j] = rng() % 10 ? 'X' : '.';
                }
            }
            int cur = calc(); if(cur > K) continue;
            for(int i = L; i < n; i++){
                for(int j = m - 2; j >= 0; j--){
                    c[i][j] = 'X';
                    if(calc() > K){
                        c[i][j] = '.';
                    }
                }
            }
            if(calc() == K){
                output();
                return;
            }
        }
    }
}
 
int32_t main(){
	int K; cin >> K;
	part2(K);
}

Subtask #1
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 408 ms 8148 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Execution timed out 651 ms 8180 KB Time limit exceeded
2 Halted 0 ms 0 KB -