Submission #789136

#	Time	Username	Problem	Language	Result	Execution time	Memory
789136		NothingXD	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	212 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out() {cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;

int n, k, dp[maxn], pd[maxn];
string ans;
vector<int> x, y;

string solve_puzzle(std::string s, std::vector<int> c) {
	n = s.size();
	k = c.size();
	for (int i = 0; i < n; i++){
		if (s[i] == 'X') x.push_back(i);
		else if (s[i] == '_') y.push_back(i);
	}
	int ptr = -1;
	for (int i = 0; i < k; i++){
		ptr++;
		while(true){
			int idx = lower_bound(all(y), ptr) - y.begin();
			if (idx != y.size() && y[idx] < ptr + c[i]) ptr++;
			else break;
		}
		dp[i] = ptr + c[i] - 1;
		ptr = dp[i] + 1;
	}
	ptr = n;
	for (int i = k-1; ~i; i--){
		ptr--;
		while(true){
			int idx = lower_bound(all(y), ptr-c[i]+1) - y.begin();
			if (idx != y.size() && y[idx] <= ptr) ptr--;
			else break;
		}
		pd[i] = ptr - c[i] + 1;
		ptr = pd[i] - 1;
	}
	ans = s;
	for (int i = 0; i < n; i++){
		if (ans[i] != '.') continue;
		bool flg1 = false, flg2 = false;
		int tmp = lower_bound(all(y), i) - y.begin();
		int l = 0, r = n-1;
		if (tmp != 0){
			l = y[tmp-1] + 1;
		}
		if (tmp != y.size()){
			r = y[tmp] - 1;
		}
		for (int j = 0; j < k; j++){
			int L = l, R = r;
			if (j) L = max(L, dp[j-1] + 2);
			if (k-j-1) R = min(R, pd[j+1] - 2);
			if (L <= i && i <= R && R - L + 1 >= c[j]){
				flg1 = true;
			}
		}
		tmp = lower_bound(all(x), i) - x.begin();
		l = 0, r = n-1;
		if (tmp != 0) l = x[tmp-1] + 1;
		if (tmp != x.size()) r = x[tmp] - 1;
		for (int j = 0; j <= k; j++){
			int L = l, R = r;
			if (j) L = max(L, dp[j-1] + 1);
			if (k-j) R = min(R, pd[j] - 1);
			if (L <= i && i <= R){
				flg2 = true;
			}
		}
		if (flg1 && flg2) ans[i] = '?';
		else if (flg1) ans[i] = 'X';
		else ans[i] = '_';
	}
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:45:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    if (idx != y.size() && y[idx] < ptr + c[i]) ptr++;
      |        ~~~~^~~~~~~~~~~
paint.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    if (idx != y.size() && y[idx] <= ptr) ptr--;
      |        ~~~~^~~~~~~~~~~
paint.cpp:71:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   if (tmp != y.size()){
      |       ~~~~^~~~~~~~~~~
paint.cpp:85:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   if (tmp != x.size()) r = x[tmp] - 1;
      |       ~~~~^~~~~~~~~~~

• 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