Submission #115094

#	Time	Username	Problem	Language	Result	Execution time	Memory
115094		E869120	Paint By Numbers (IOI16_paint)	C++14	32 / 100	3 ms	384 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

int N, K, cl[109], cr[109];
vector<int>vec;

bool ranged(int pl, int pr) {
	int pos1 = lower_bound(vec.begin(), vec.end(), pl) - vec.begin();
	int pos2 = lower_bound(vec.begin(), vec.end(), pr) - vec.begin();
	if (pos2 - pos1 >= 1) return true;
	return false;
}

string solve_puzzle(string s, vector<int> c) {
	N = s.size(); K = c.size();
	for (int i = 0; i < s.size(); i++) { if (s[i] == '_') vec.push_back(i); }
	
	cl[0] = -1;
	for (int i = 1; i <= K; i++) {
		cl[i] = cl[i - 1] + c[i - 1] + 1;
		while (ranged(cl[i] - c[i - 1] + 1, cl[i]) == true) cl[i]++;
	}
	cr[K] = N + 1;
	for (int i = K - 1; i >= 0; i--) {
		cr[i] = cr[i + 1] - c[i] - 1;
		while (ranged(cr[i], cr[i] + c[i] - 1) == true) cr[i]--;
	}
	
	string str = "";
	for (int i = 0; i < N; i++) {
		if (s[i] == '_') str += '_';
		else if (s[i] == 'X') str += 'X';
		else {
			bool p1 = false, p2 = false;
			for (int j = 0; j <= K; j++) {
				if (cl[j] <= i && i < cr[j]) p1 = true;
			}
			int pos1 = lower_bound(vec.begin(), vec.end(), i) - vec.begin(); pos1--;
			int pos2 = lower_bound(vec.begin(), vec.end(), i) - vec.begin();
			int ul = -1; if (pos1 >= 0) ul = vec[pos1];
			int ur = N; if (pos2 < vec.size()) ur = vec[pos2];
			
			for (int j = 0; j <= K - 1; j++) {
				int V1 = max(cl[j] + 1, ul + 1);
				int V2 = min(cr[j + 1] - 1, ur);
				//cout << i << " " << V1 << " " << V2 << " " << j << " " << c[j] << endl;
				if (V2 - V1 >= c[j] && V1 <= i && i < V2) p2 = true;
			}
			
			if (p1 == true && p2 == true) str += '?';
			else if (p1 == true) str += '_';
			else str += 'X';
		}
	}
	return str;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) { if (s[i] == '_') vec.push_back(i); }
                  ~~^~~~~~~~~~
paint.cpp:42:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    int ur = N; if (pos2 < vec.size()) ur = vec[pos2];
                    ~~~~~^~~~~~~~~~~~

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