Submission #722228

#	Time	Username	Problem	Language	Result	Execution time	Memory
722228		baojiaopisu	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	340 KiB

paint

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 2e5 + 10;
const int K = 105;

int f[N][K], g[N][K], d[N];
int pref[N];

string solve_puzzle(string s, vector<int> c) {
	string ans = "";
	int n = s.size();
	s = "#" + s;

	for(int i = 1; i <= n; i++) {
		pref[i] = pref[i - 1] + (s[i] == '_');
	}

	int k = c.size();
	f[0][0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < c.size(); j++) {
			if(s[i] != 'X') f[i][j + 1] = (f[i][j + 1] + f[i - 1][j + 1]) % MOD;
			int l = i - c[j] + 1;
			if(l < 1 || pref[i] != pref[l - 1] || s[l - 1] == 'X') continue;
			f[i][j + 1] = (f[i][j + 1] + f[(l == 1 ? l - 1 : l - 2)][j]) % MOD;
		}
		if(s[i] != 'X') f[i][0] = f[i - 1][0];
	}

	g[n + 1][c.size() + 1] = 1;
	for(int i = n; i >= 1; i--) {
		for(int j = 0; j < c.size(); j++) {
			if(s[i] != 'X') g[i][j + 1] = (g[i][j + 1] + g[i + 1][j + 1]) % MOD;
			int r = i + c[j] - 1;
			if(r > n || pref[r] != pref[i - 1] || (r < n && s[r + 1] == 'X')) continue;
			g[i][j + 1] = (g[i][j + 1] + g[(r == n ? r + 1 : r + 2)][j + 2]) % MOD;
		}
		if(s[i] != 'X') g[i][k + 1] = g[i + 1][k + 1];
	}

	for(int i = 1; i <= n; i++) {
		if(s[i] == '.') {
			ll ans = 0;
			for(int j = 0; j <= k; j++) {
				ans += 1ll * f[i - 1][j] * g[i + 1][j + 1] % MOD;
				ans %= MOD;
			}

			if(ans == f[n][k]) s[i] = '_';
		}
	}

	for(int i = 1; i <= n; i++) {
		pref[i] = pref[i - 1] + (s[i] == '_');
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= k; j++) {
			int r = i + c[j - 1] - 1;
			if(r > n) continue;
			if(pref[r] != pref[i - 1] || s[i - 1] == 'X' || (r < n && s[r + 1] == 'X')) continue;
			d[i] += 1ll * f[(i == 1 ? i - 1 : i - 2)][j - 1] * g[(r == n ? r + 1 : r + 2)][j + 1] % MOD;
			d[r + 1] -= 1ll * f[(i == 1 ? i - 1 : i - 2)][j - 1] * g[(r == n ? r + 1 : r + 2)][j + 1] % MOD;
			d[i] %= MOD;
			d[r + 1] %= MOD;
		}
	}

	for(int i = 1; i <= n; i++) {
		d[i] += d[i - 1];
		d[i] = (d[i] + MOD) % MOD;
		if(d[i] == f[n][k] && s[i] == '.') s[i] = 'X';
	}

	string res = "";
	for(int i = 1; i <= n; i++) {
		res += s[i];
		if(res.back() == '.') res[i - 1] = '?';
	}

	return res;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for(int j = 0; j < c.size(); j++) {
      |                  ~~^~~~~~~~~~
paint.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int j = 0; j < c.size(); j++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10