Submission #810377

#	Time	Username	Problem	Language	Result	Execution time	Memory
810377		QwertyPi	Costinland (info1cup19_costinland)	C++14	0 / 100	257 ms	400 KiB

costinland

#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 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' : '.';
                }
            }
            __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;
	part2(K);
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80