Submission #405900

#	Time	Username	Problem	Language	Result	Execution time	Memory
405900		Kevin_Zhang_TW	Paint By Numbers (IOI16_paint)	C++17	0 / 100	12 ms	460 KiB

paint

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

#include "paint.h"
const int MAX_N = 200010, MAX_K = 105;

bool dp1[MAX_N][MAX_K], dp2[MAX_N][MAX_K], ok[MAX_N][MAX_K];
int from1[MAX_N][MAX_K], from2[MAX_N][MAX_K];
char w[MAX_N];
int pf0[MAX_N], pf1[MAX_N], n;
int be0[MAX_N], be1[MAX_N];
int len[MAX_K], m;

int cnt1(int l, int r) { return pf1[r] - pf1[l-1]; }
int cnt0(int l, int r) { return pf0[r] - pf0[l-1]; }

void makedp1() {
	for (int i = len[1];i <= n;++i) 
		dp1[i][1] = cnt0(i-len[1]+1, i) == 0 && cnt1(1, i-len[1]) == 0;
	
	vector<int> f(m + 1);
	for (int i = 1;i <= n;++i) {
		for (int j = 2;j <= m;++j) {
			if (len[j] > i || w[i-len[j]] == 'X') continue;
			int &k = f[j];
			while (k < i - len[j] &&
					(!dp1[k][j-1] || cnt1(k+1, i-len[j]))) ++k;
			if (k < i - len[j]) {
				DE(i, j);
				dp1[i][j] = true;
				from1[i][j] = k;
			}
		}
	}
}
void makedp2() {
	for (int i = 1;i <= n - len[m] + 1;++i) {
		dp2[i][m] = cnt0(i, i+len[m]-1) == 0 && cnt1(i+len[m], n) == 0;
		from2[i][m] = n + 1;
	}

	vector<int> f(m + 1, n + 1);
	for (int i = n;i >= 1;--i) {
		for (int j = 1;j < m;++j) {
			if (i + len[j] - 1 > n || w[i+len[j]] == 'X') continue;
			int &k = f[j];
			while (k > i + len[j] &&
					(!dp2[k][j+1] || cnt1(i+len[j], k-1))) --k;
			if (k > i + len[j]) {
				dp2[i][j] = true;
				from2[i][j] = k;
			}
		}
	}
}

void collect() {
	DE(dp1[8][2], dp2[5][2]);
	for (int i = 1;i <= n;++i) {
		for (int j = 1;j <= m;++j) {
			if (dp1[i][j] && dp2[i - len[j] + 1][j]) {
//			ok[i][j] = dp1[i][j] && dp2[i - len[j] + 1][j];
//			if (ok[i][j]) {
				DE(i, len[j]);
				++be1[i - len[j] + 1];
				--be1[i + 1];

				++be0[ from1[i][j] + 1 ];
				--be0[ i - len[j] + 1];

				DE(i+1, from2[i - len[j] + 1][j]);
				++be0[ i + 1 ];
				--be0[ from2[i - len[j] + 1][j] ];
			}
		}
	}
	for (int i = 1;i <= n;++i) {
		be1[i] += be1[i-1];
		be0[i] += be0[i-1];
	}
}
std::string solve_puzzle(std::string s, std::vector<int> c) {
	static int cnt;
	assert(++cnt == 1);
	n = s.size();
	for (int i = 1;i <= n;++i) {
		pf0[i] = pf0[i-1] + (s[i-1] == '_');
		pf1[i] = pf1[i-1] + (s[i-1] == 'X');
		w[i] = s[i-1];
	}
	m = c.size();
	for (int i = 1;i <= m;++i)
		len[i] = c[i-1];

	makedp1();
	makedp2();
	collect();

	string res(n, '?');

	for (int i = 1;i <= n;++i) {
		DE(i, be0[i], be1[i]);
		if (be0[i] && !be1[i])
			res[i-1] = '_';
		if (!be0[i] && be1[i])
			res[i-1] = 'X';
	}
	for (int i = 0;i < n;++i)
		if (s[i] != '?') assert(res[i] == s[i]);

	return res;
}

Compilation message (stderr)

paint.cpp: In function 'void makedp1()':
paint.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
paint.cpp:43:5: note: in expansion of macro 'DE'
   43 |     DE(i, j);
      |     ^~
paint.cpp: In function 'void collect()':
paint.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
paint.cpp:72:2: note: in expansion of macro 'DE'
   72 |  DE(dp1[8][2], dp2[5][2]);
      |  ^~
paint.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
paint.cpp:78:5: note: in expansion of macro 'DE'
   78 |     DE(i, len[j]);
      |     ^~
paint.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
paint.cpp:85:5: note: in expansion of macro 'DE'
   85 |     DE(i+1, from2[i - len[j] + 1][j]);
      |     ^~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
paint.cpp:116:3: note: in expansion of macro 'DE'
  116 |   DE(i, be0[i], be1[i]);
      |   ^~

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