Submission #889657

#	Time	Username	Problem	Language	Result	Execution time	Memory
889657		UmairAhmadMirza	Paint By Numbers (IOI16_paint)	C++17	32 / 100	1 ms	348 KiB

paint

#pragma once

#include<bits/stdc++.h>
using namespace std;
int k=0;
string s;
vector<int> c;
int n;
int const N=105;
int pre[N][N];
int suf[N][N];
bool check(int a,int b,int l,int r){
	if(a>b)
		return 1;
	int p=a;
	int ind=l;
	while(p<=b){
		if(ind+c[p]>(r+1))
			return 0;
		bool bl=1;
		for (int i = ind; i < ind+c[p]; ++i)
			if(s[i]=='_')
				bl=0;
		if(bl){
			ind+=c[p];
			p++;
			if(p<=b)
				ind++;
		}
		else
			ind++;
	}
	return 1;
}
void preprocess(){
	for (int i = -1; i < n; ++i)
		for (int j = -1; j < k; ++j)
			pre[i+1][j+1]=check(0,j,0,i);
	for (int i = n; i>=0; --i)
		for(int j=k;j>=0;j--)
			suf[i][j]=check(j,k-1,i,n-1);
}
string solve_puzzle(string ss, vector<int> cc){
	k=cc.size();
	c=cc;
	s=ss;
	n=s.length();
	preprocess();
	for (int i = 0; i < n; ++i)
	{
		//if i put a _ here then check that is there a valid solution
		s[i]='X';
		for (int j = -1; j < k; ++j)
			if(pre[i][j+1] && suf[i+1][j+1]){
				s[i]='?';
				break;
			}
	}
	int tot=0;
	for (int i = 0; i < k; ++i)
		tot+=c[i];
	for (int i = 0; i < n; ++i)
	{
		if(s[i]=='X')
			continue;
		int sm=0;
		s[i]='_';
		for (int j = 0; j < k; ++j)
		{
			for (int f = max(0,(i-c[j])+1); f <=i; ++f)
			{
				int smm=sm+j;
				if(smm>=f+1)
					continue;
				smm=tot-sm;
				smm+=k-(j+1);
				if(smm<=n-f){
					s[i]='?';
					break;
				}
			}
			if(s[i]=='?')
				break;
			sm+=c[j];
		}
	}
	return s;
}

Compilation message (stderr)

paint.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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