Submission #121949

#	Time	Username	Problem	Language	Result	Execution time	Memory
121949		khulegub	Paint By Numbers (IOI16_paint)	C++14	59 / 100	2 ms	384 KiB

paint

#include "paint.h"
#include<cstdlib>
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second
using namespace std;





string solve_puzzle(string s, vector<int> c) {
	string s_orig = s;
	vector<pair<int, string> > segg;
	vector<pair<int, string> > seg;
	int n = s.length();
	int cn = c.size();
	segg.pb( mp(0, "") );
	for (int i = 0; i < n; i++){
		if(s[i] == '_') segg.pb( mp(i + 1, "") );
		else segg.back().yy.pb(s[i]);
	}
	for (auto segment : segg){
		if(segment.yy.size() > 0) seg.pb(segment);
	}
	for (int ci = 0; ci < cn; ci++){
		int lseg = 0, lsegi = 0;
		for(int cii = 0; cii < ci; cii++){
			while(true){
				if(seg[lseg].yy.size() >= lsegi + c[cii]){
					lsegi = lsegi + c[cii] + 1;
					break;
				}
				else{
					lseg++;
					lsegi = 0;
				}
			}
		}
		//ci ni lseg t bagtahnu
		if(seg[lseg].yy.size() < lsegi + c[ci]){ //bagtkum bna
			//daraachin dajgu segment iig oloh
			while(true){
				lseg++;
				if(seg[lseg].yy.size() >= c[ci]){
					lsegi = 0;
					break;
				}
			}
		}

		int rseg = seg.size() - 1, rsegi = seg[rseg].yy.size() - 1;
		for (int cii = cn - 1; cii > ci; cii--){
			while(true){
				if(rsegi - c[cii] >= -1){
					rsegi = rsegi - c[cii] - 1;
					break;
				}
				else{
					rseg--;
					rsegi = seg[rseg].yy.size() - 1;
				}
			}
		}
		// blba
		if(-1 > rsegi - c[ci]){
			while(true){
				rseg--;
				if(seg[rseg].yy.size() >= c[ci]){
					rsegi = seg[rseg].yy.size() - 1;
					break;
				}
			}
		}

		for(int si = lseg; si <= rseg; si++){
			int l = 0, r = seg[si].yy.size() - 1;
			if(si == lseg) l = lsegi;
			if(si == rseg) r = rsegi;

			l += seg[si].xx;
			r += seg[si].xx;
			//segmented bagtah esehee shalga
			if( r - l + 1 >= c[ci]){
				int rx = -1, lx = -1;
				for (int i = l; i <= r; i++){
					if(s_orig[i] == 'X'){
						if(lx == -1) lx = i;
						rx = i;
					}
				}
				if(rx != -1){
					if(l + c[ci] - 1 < rx){
						l = rx - c[ci] + 1;
					}
					if(r - c[ci] + 1 > lx) r = lx + c[ci] -1;

				}
				int sz = r - l + 1;
				int davhtsal = 2*c[ci] - sz;
				if (davhtsal > 0){
					for (int i = r - c[ci] + 1; i <= r - c[ci] + davhtsal; i++){
						if(s[i] == '.'){
							if(lseg == rseg) s[i] = 'X';
							else s[i] = '?';
						}
					}
				}
				for (int i = l; i <= r; i++){
					if (i < r - c[ci] + 1 || i > r - c[ci] + davhtsal) s[i] = '?';
				}
				
			}
		}
		// cout << lseg << ' ' << lsegi << endl;
		// cout << rseg << ' ' << rsegi << endl;
		// cout << "$$$$$$$$$$$$$$$$$\n";
	}
	for(int i = 0; i < n; i++) if(s[i] == '.') s[i] = '_';
	// cout << s;
    return s;
}

Compilation message (stderr)

paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:32:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(seg[lseg].yy.size() >= lsegi + c[cii]){
paint.cpp:43:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(seg[lseg].yy.size() < lsegi + c[ci]){ //bagtkum bna
paint.cpp:47:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(seg[lseg].yy.size() >= c[ci]){
paint.cpp:71:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(seg[rseg].yy.size() >= c[ci]){

• 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