Submission #943352

#	Time	Username	Problem	Language	Result	Execution time	Memory
943352		Nika533	Paint By Numbers (IOI16_paint)	C++14	59 / 100	1 ms	600 KiB

paint

#pragma GCC diagnostic warning "-std=c++11"
#include <bits/stdc++.h>
#include "paint.h"
#define pb push_back
#define MOD 1000000007
#define flush fflush(stdout)
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define pii pair<int,int>
using namespace std;
string solve_puzzle(string s, vector<int> c) {
   int n=s.size(); int k=c.size();
   
   int pref[k+5],suf[k+5]; suf[k]=1e9;
   int ind;
   ind=-1;
   for (int i=0; i<c.size(); i++) {
   	int last=ind; ind++;
   	for (ind; ind<n; ind++) {
   		if (s[ind]=='_') last=ind;
   		if (ind-last>=c[i]) break;
		}
		pref[i]=ind;
		ind++;
	}
	ind=n;
	for (int i=c.size()-1; i>=0; i--) {
		int last=ind; ind--;
		for (ind; ind>=0; ind--) {
			if (s[ind]=='_') last=ind;
			if (last-ind>=c[i]) break;
		}
		suf[i]=ind;
		ind--;
	}
	string ans=s;
	for (int i=0; i<n; i++) {
		bool canBeWhite=0,canBeBlack=0;
		// can be '_'
		if (suf[0]>i) canBeWhite=1;
		for (int j=0; j<k; j++) {
			if (pref[j]<i && i<suf[j+1]) canBeWhite=1;
		}
		// can be 'X'
		int lb=-1,rb=n;
		for (int j=i; j>=0; j--) {
			if (s[j]=='_') {
				lb=j; break;
			}
		}
		for (int j=i; j<n; j++) {
			if (s[j]=='_') {
				rb=j; break;
			}
		}
		for (int j=0; j<k; j++) {
			for (int o=0; o<c[j]; o++) {
				if ((i-o)<=lb || rb<=(i+c[j]-o-1)) continue;
				int num1=(i-o)-1,num2=(i+c[j]-o-1)+1;
				if ((j==0 || pref[j-1]<num1) && (j==k-1 || suf[j+1]>num2)) canBeBlack=1;
			}
		}
		if (canBeBlack==1 && canBeWhite==1) ans[i]='?';
		else if (canBeBlack==1) ans[i]='X';
		else ans[i]='_';
	}
	return ans;
}

Compilation message (stderr)

paint.cpp:1:32: warning: '-std=c++11' is not an option that controls warnings [-Wpragmas]
    1 | #pragma GCC diagnostic warning "-std=c++11"
      |                                ^~~~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |    for (int i=0; i<c.size(); i++) {
      |                  ~^~~~~~~~~
paint.cpp:19:10: warning: statement has no effect [-Wunused-value]
   19 |     for (ind; ind<n; ind++) {
      |          ^~~
paint.cpp:29:8: warning: statement has no effect [-Wunused-value]
   29 |   for (ind; ind>=0; ind--) {
      |        ^~~

• 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