Submission #290298

#	Time	Username	Problem	Language	Result	Execution time	Memory
290298		shayan_p	Paint By Numbers (IOI16_paint)	C++17	Compilation error	0 ms	0 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k)) & 1)
#define any STRANGE

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 2e5 + 10, maxk = 110, mod = 1e9 + 7, inf = 1e9 + 10;

bool dp[2][maxk][maxn], frs[2][maxk][maxn];
int sm[maxn];

bool any(int l, int r){
    return sm[r] - sm[l-1] > 0;
}
bool solve(string &s, vector<int> &c, int dp[maxk][maxn], int frs[maxk][maxn]){
    for(int i = 0; i <= sz(c); i++)
	frs[i] = inf;
    frs[0] = 0;
    dp[0][0] = 1;
    for(int i = 0; i <= sz(c); i++){
	for(int j = 1; j <= sz(s); j++){
	    dp[i][j] = 0;
	    if(s[j-1] != 'X')
		dp[i][j]|= dp[i][j-1];
	    if(i > 0){
		if(j > c[i-1])
		    dp[i][j]|= !any(j-c[i-1]+1, j) && s[j-1-c[i-1]] != 'X' && dp[i-1][j-c[i-1]-1];
		if(j == c[i-1])
		    dp[i][j]|= !any(1, j) && i == 1;
	    }
	}
    }
    for(int i = 0; i <= sz(c); i++){
	frs[i][sz(s) + 1] = sz(s) + 1;
	for(int j = sz(s); j >= 0; j--){
	    bool ok = 0;
	    if(j == 0)
		ok = i == 0;
	    else
		ok = dp[i][j-1];
	    if(ok)
		frs[i][j] = j;
	    else
		frs[i][j] = frs[i][j+1];
	}
    }    
    return dp[sz(c)][sz(s)];
}

int pre[maxn], aft[maxn];

string solve_puzzle(string s, vector<int> c){
    for(int i = 1; i <= sz(s); i++){
	if(s[i-1] == '_')
	    pre[i] = i;
	else
	    pre[i] = pre[i-1];
    }
    pre[sz(s) + 1] = sz(s) + 1;
    for(int i = sz(s); i >= 1; i--){
	if(s[i-1] == '_')
	    aft[i] = i;
	else
	    aft[i] = aft[i+1];   
    }    
    for(int i = 1; i <= sz(s); i++){
	sm[i] = sm[i-1] + (s[i-1] == '_');
    }
    solve(s, c, dp[0]);
    reverse(s.begin(), s.end());
    solve(s, c, dp[1]);
    reverse(s.begin(), s.end());
    
    string ans = s;
    for(int i = 0; i < sz(s); i++){
	if(s[i] == '.'){
	    bool A = 0, B = 0;
	    for(int j = 0; j < sz(c); j++){
		int l = frs[0][j][pre[i]], r = sz(s) + 1 - frs[1][sz(c)-1-j][sz(s)-aft[i]+1];
		A|= r-l-1 >= c[j] && l < i+1 && i+1 < r;
	    }
	    for(int j = 0; j <= sz(c); j++){
		B|= dp[0][w][i] && dp[1][sz(c)-w][sz(s)-i-1];		
	    }
	    if(A && B)
		ans[i] = '?';
	    else if(A)
		ans[i] = 'X';
	    else if(B)
		ans[i] = '_';
	    else
		assert(0);
	    s[i] = '.';		
	}		    
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool solve(std::string&, std::vector<int>&, int (*)[200010], int (*)[200010])':
paint.cpp:26:11: error: incompatible types in assignment of 'const int' to 'int [200010]'
   26 |  frs[i] = inf;
      |           ^~~
paint.cpp:27:14: error: incompatible types in assignment of 'int' to 'int [200010]'
   27 |     frs[0] = 0;
      |              ^
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:78:21: error: cannot convert 'bool (*)[200010]' to 'int (*)[200010]'
   78 |     solve(s, c, dp[0]);
      |                 ~~~~^
      |                     |
      |                     bool (*)[200010]
paint.cpp:24:43: note:   initializing argument 3 of 'bool solve(std::string&, std::vector<int>&, int (*)[200010], int (*)[200010])'
   24 | bool solve(string &s, vector<int> &c, int dp[maxk][maxn], int frs[maxk][maxn]){
      |                                       ~~~~^~~~~~~~~~~~~~
paint.cpp:80:21: error: cannot convert 'bool (*)[200010]' to 'int (*)[200010]'
   80 |     solve(s, c, dp[1]);
      |                 ~~~~^
      |                     |
      |                     bool (*)[200010]
paint.cpp:24:43: note:   initializing argument 3 of 'bool solve(std::string&, std::vector<int>&, int (*)[200010], int (*)[200010])'
   24 | bool solve(string &s, vector<int> &c, int dp[maxk][maxn], int frs[maxk][maxn]){
      |                                       ~~~~^~~~~~~~~~~~~~
paint.cpp:92:13: error: 'w' was not declared in this scope
   92 |   B|= dp[0][w][i] && dp[1][sz(c)-w][sz(s)-i-1];
      |             ^