Submission #758948

#	Time	Username	Problem	Language	Result	Execution time	Memory
758948		minhcool	Paint By Numbers (IOI16_paint)	C++17	0 / 100	4 ms	7380 KiB

paint

//#define local
#ifndef local
#include "paint.h"
#endif
 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
//#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 3e5 + 5;
 
const int oo = 1e18 + 7, mod = 1e9 + 7;
 
mt19937 rng(1);
 
int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}
 
int pref0[N], pref1[N];
 
vector<int> okay[N];
 
int lst[105][N];
 
string solve_puzzle(string s, vector<int> c) {
    //return "";
    int n = s.length();
    s = '*' + s;
    for(int i = 1; i <= n; i++){
    	pref0[i] = (pref0[i - 1] + (s[i] == '_'));
    	pref1[i] = (pref1[i - 1] + (s[i] == 'X'));
	}
	okay[0].pb(-1);
	for(int i = 1; i <= c.size(); i++){
		int temp = c[i - 1];
		int itr = -1;
		for(int j = 1; j <= n; j++){
			itr = max(itr, 0);
			while(itr < okay[i - 1].size() && okay[i - 1][itr] < (j - temp)) itr++;
			itr--;
			if(itr < 0) continue;
			if(pref0[j] > pref0[okay[i - 1][itr]]) continue;
			if(pref1[j - temp] > pref1[okay[i - 1][itr]]) continue;
			okay[i].pb(j);
			lst[i][j] = okay[i - 1][itr];
			//cout << i << " " << j << "\n";
		}
	}
//	exit(0);
	assert(okay[c.size()].size());
	int itr = okay[c.size()].back();
	for(int i = itr + 1; i <= n; i++) s[i] = '_';
	for(int i = c.size(); i >= 1; i--){
		int temp = c[i - 1];
		for(int j = itr; j > lst[i][itr]; j--){
			if((itr - j) < c[i - 1]) s[j] = 'X';
			else s[j] = '_';
		}
		itr = lst[i][itr];
	}
	return s.substr(1);
}
 
//#define local
#ifdef local
void process(){
	string s;
	int n;
	cin >> s >> n;
	vector<int> v;
	while(n--){
		int x;
		cin >> x;
		v.pb(x);
	}
	cout << solve_puzzle(s, v) << "\n";
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif local

Compilation message (stderr)

paint.cpp:97:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
   97 | #endif local
      |        ^~~~~
paint.cpp:23:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 1; i <= c.size(); i++){
      |                 ~~^~~~~~~~~~~
paint.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |    while(itr < okay[i - 1].size() && okay[i - 1][itr] < (j - temp)) itr++;
      |          ~~~~^~~~~~~~~~~~~~~~~~~~
paint.cpp:67:7: warning: unused variable 'temp' [-Wunused-variable]
   67 |   int temp = c[i - 1];
      |       ^~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10