Submission #139706

#	Time	Username	Problem	Language	Result	Execution time	Memory
139706		SirCeness	Paint By Numbers (IOI16_paint)	C++14	59 / 100	5 ms	504 KiB

paint

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

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
#define orta ((l+r)>>1)
#define INF 1000000009
#define mod 1000000007
#define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n";
#define bas(x) #x << ": " << x << " "
#define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n";
#define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n";
using namespace std;
typedef long long ll;

string s;
int pre[101];
string ans;
int varmi(int l, int r){
	int ans = 0;
	if (l == 0) ans = pre[r];
	else ans = pre[r] - pre[l-1];
	if (ans > 0) return 1;
	else return 0;
}

int possible(int l, int r, vector<int>& c){
	if (c.size() == 0) return 1;
	if (r-l+1 < c.back()) return 0;
	if (varmi(r-c.back()+1, r)) return possible(l, r-1, c);
	r -= c.back();
	r--;
	c.pop_back();
	return possible(l, r, c);
}

void merge(int i, char c){
	if (ans[i] == '!') ans[i] = c;
	else if (ans[i] == '_' && c == 'X') ans[i] = '?';
	else if (ans[i] == 'X' && c == '_') ans[i] = '?';
	else if (ans[i] == '_' && c == '?') ans[i] = '?';
	else if (ans[i] == 'X' && c == '?') ans[i] = '?';
}

void solve(int l, int r, vector<int>& c){
	//cout << "solve(" << l << ", " << r << ", "; prarrv(c);
	if (c.size() == 0){
		for (int i = l; i <= r; i++){
			merge(i, '_');
		}
	} else {
		vector<int> presum(c.size());
		presum[0] = c[0];
		string str(r-l+1, '?');
		for (int i = 1; i < c.size(); i++) presum[i] = presum[i-1] + c[i];
		if (presum[c.size()-1] + c.size()-1 > r-l+1) return;
		else if (presum[c.size()-1] + c.size()-1 == r-l+1){
			string str = "";
			for (int i = 0; i < c.size(); i++){
				for (int j = 0; j < c[i]; j++) str += "X";
				if (i != c.size()-1) str += "_";
			}
			for (int i = 0; i < str.size(); i++) merge(i+l, str[i]);
			return;
		}
		for (int i = 0; i < c.size(); i++){
			int sag = presum[i] + i;
			int sol = presum[c.size()-1] - (i == 0 ? 0 : presum[i-1]) + c.size()-1-i;
			sol = r-l+1-sol;
			//cout << bas(sol) << bas(sag) << endl;
			//if (sol < 0 || sag > str.size()) continue;
			for (int k = sol; k < sag; k++) str[k] = 'X';
		}
		for (int i = 0; i < str.size(); i++) merge(i+l, str[i]);
	}
}

vector<int> subv(int l, int r, vector<int>& arr){
	vector<int> ans;
	for (int i = l; i <= r; i++) ans.pb(arr[i]);
	return ans;
}

string solve_puzzle(string S, vector<int> c) {
    s = S;
	int sum = 0;
	for (int i = 0; i < s.size(); i++){
		if (s[i] == '_') sum++;
		pre[i] = sum;
	}
	ans = "";
	for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
	vector<pair<int, int> > araliklar;
	int last = -1;
	for (int i = 0; i < s.size(); i++){
		if (s[i] == '_'){
			if (last != i-1) araliklar.pb(mp(last, i));
			last = i;
		}
	}
	//cout << ans << endl;
	araliklar.pb(mp(last, s.size()));
	//for (int i = 0; i < araliklar.size(); i++) {ppair(araliklar[i]);}
	for (int l = -1; l < (int)c.size(); l++){
		for (int r = l+1; r <= c.size(); r++){
			for (int i = 0; i < araliklar.size(); i++){
				vector<int> v1 = subv(0, l, c);
				vector<int> v2 = subv(r, c.size()-1, c);
				//cout << "0 - " << araliklar[i].first << ": "; prarrv(v1);
				//cout << araliklar[i].second << " - " << s.size()-1 << ": "; prarrv(v2);
				if (possible(0, araliklar[i].first, v1) && 
				possible(araliklar[i].second, s.size()-1, v2)){
					//cout << "possible" << endl;
					vector<int> sv = subv(l+1, r-1, c);
					solve(araliklar[i].first+1, araliklar[i].second-1, sv);
					//cout << ans << endl;
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'void solve(int, int, std::vector<int>&)':
paint.cpp:57:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < c.size(); i++) presum[i] = presum[i-1] + c[i];
                   ~~^~~~~~~~~~
paint.cpp:58:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (presum[c.size()-1] + c.size()-1 > r-l+1) return;
paint.cpp:59:44: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   else if (presum[c.size()-1] + c.size()-1 == r-l+1){
paint.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < c.size(); i++){
                    ~~^~~~~~~~~~
paint.cpp:63:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i != c.size()-1) str += "_";
         ~~^~~~~~~~~~~~~
paint.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < str.size(); i++) merge(i+l, str[i]);
                    ~~^~~~~~~~~~~~
paint.cpp:68:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < c.size(); i++){
                   ~~^~~~~~~~~~
paint.cpp:76:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < str.size(); i++) merge(i+l, str[i]);
                   ~~^~~~~~~~~~~~
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++){
                  ~~^~~~~~~~~~
paint.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
                  ~~^~~~~~~~~~
paint.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++){
                  ~~^~~~~~~~~~
paint.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int r = l+1; r <= c.size(); r++){
                     ~~^~~~~~~~~~~
paint.cpp:108:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < araliklar.size(); i++){
                    ~~^~~~~~~~~~~~~~~~~~

• 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