Submission #966889

#	Time	Username	Problem	Language	Result	Execution time	Memory
966889		ByeWorld	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	448 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5+10;
const int INF = 1e9+10;
typedef pair<int,int> pii;

void chmx(int &a, int b){
	a = max(a, b);
}

int n, siz;
int bla[MAXN], whi[MAXN], pr[MAXN], su[MAXN], can[MAXN];
int mxpr[MAXN], mxsu[MAXN];
vector <int> c;
vector <pii> seg;
string ans;

string solve_puzzle(string s, vector<int> C) {
	s = '_'+s+'_'; n = s.size()-2;
	for(int i=1; i<=n; i++){
		bla[i] = bla[i-1]; whi[i] = whi[i-1];
		if(s[i]=='_') whi[i]++;
		if(s[i]=='X') bla[i]++;
	}
	whi[n+1] = whi[n]; c.pb(-1);
	for(auto in : C) c.pb(in);
	siz = c.size()-1;

	for(int r=1; r<=n; r++){
		pr[r] = 0;
		for(int idx=1; idx<c.size(); idx++){
			int len = c[idx], l = r-len+1;
			if(l <= 0) continue; // negatif
			int num = whi[r]-whi[l-1];
			if(l==1){
				if(num==0 && idx==1){
					chmx(pr[r], 1);
				}
			} else { // l>=2
				if(num==0 && s[l-1]!='X' && pr[l-2]>=idx-1){
					chmx(pr[r], idx);
				}
			}
		}
	}
	pr[n+1] = pr[n];
	for(int i=1; i<=n+1; i++) mxpr[i] = max(mxpr[i-1], pr[i]);

	for(int l=n; l>=1; l--){
		su[l] = 0;
		for(int idx=c.size()-1; idx>=1; idx--){
			int len = c[idx], r = l+len-1;
			if(r >= n+1) continue; // negatif
			int num = whi[r]-whi[l-1];
			if(r==n){
				if(num==0 && idx==c.size()-1){
					chmx(su[l], 1);
					if(mxpr[max(0, l-2)]+su[l] >= siz) seg.pb({l, r});
					// cout << l << " su\n";
				}
			} else { // l>=2
				if(num==0 && s[r+1]!='X' && su[r+2]>=siz-idx){
					chmx(su[l], siz-idx+1);
					if(mxpr[max(0, l-2)]+su[l] >= siz) seg.pb({l, r});
					// cout << l << " kedsu\n";
				}
			}
		}
	}
	su[0] = su[1];
	for(int i=n; i>=0; i--) mxsu[i] = max(mxsu[i+1], su[i]);

	sort(seg.begin(), seg.end());
	for(int i=0; i<seg.size(); i++){
		int l = seg[i].fi, r = seg[i].se;
		while(i+1<seg.size() && seg[i+1].fi <= r){
			i++;
			chmx(r, seg[i].se);
		}
		for(int j=l; j<=r; j++) can[j] = 1;
	}
	su[0] = su[1];
	// for(int i=0; i<=n+1; i++){
	// 	cout << i << ' ' << pr[i] << ' ' << su[i] << ' '<< can[i]<< " pp\n";
	// }

	for(int i=1; i<=n; i++){
		if(s[i]=='_'){
			ans.pb('_'); continue;
		}
		if(s[i]=='X'){
			ans.pb('X'); continue;
		}
		bool W = 0, B = 0;
		if(mxpr[i-1]+mxsu[i+1] >= siz) W = 1;

		// cek black
		if(can[i]) B = 1;

		if(!W && B) ans.pb('X');
		else if(W && !B) ans.pb('_');
		else ans.pb('?');
	}
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:36:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int idx=1; idx<c.size(); idx++){
      |                  ~~~^~~~~~~~~
paint.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     if(num==0 && idx==c.size()-1){
      |                  ~~~^~~~~~~~~~~~
paint.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=0; i<seg.size(); i++){
      |               ~^~~~~~~~~~~
paint.cpp:81:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while(i+1<seg.size() && seg[i+1].fi <= r){
      |         ~~~^~~~~~~~~~~

• 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