Submission #262901

#	Time	Username	Problem	Language	Result	Execution time	Memory
262901		Evirir	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2096 ms	172088 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 200005;
const int MAXK = 105;

int n,m;
vector<int> c;
ll dp[MAXN][MAXK];
ll can[MAXN][2];
ll pre[MAXN][2];

inline bool check(int l, int r, int t)
{
	if(DEBUG) cout<<"check("<<l<<","<<r<<","<<t<<") = ";
	if(r < l){
		if(DEBUG) cout<<"default 0\n";
		return 0;
	}
	
	if(DEBUG) cout<<(pre[r][t] - (l ? pre[l-1][t] : 0LL))<<'\n';
	return pre[r][t] - (l ? pre[l-1][t] : 0LL);
}

inline void mark(int l, int r, int t)
{
	//if(DEBUG) cout<<"mark("<<l<<","<<r<<","<<t<<")"<<endl;
	if(r<0 || l>r) return;
	can[l][t]++; can[r+1][t]--;
}

bool rec(int i, int j)
{
	if(DEBUG) cout<<"rec("<<i<<","<<j<<"): start"<<'\n';
	if(j == -1) return true; //if(DEBUG) SD(1);
	if(i < 0) return false;
	if(dp[i][j] != -1) return dp[i][j]; //if(DEBUG) SD(2);
	if(i-c[j]+1 < 0) return (dp[i][j] = 0); if(DEBUG) SD(3);
	if(check(i-c[j]+1, i, 0)) return (dp[i][j] = 0); if(DEBUG) SD(4);
	
	bool ok = 0;
	for(int k=i-c[j]-1;k>=-2;k--)
	{
		if(DEBUG) cout<<"k = "<<k<<'\n';
		if(check(max(0,k+1), i-c[j], 1)) continue;
		if(j==0 && check(0, i-c[j], 1)) continue;
		if(rec(k, j-1)){
			ok = 1;
			mark(i-c[j]+1, i, 1);
			mark(max(0,k+1), i-c[j], 0);
		}
	}
	
	if(DEBUG)
	{
		ll tmp[n][2]{};
		forn(i,0,n) forn(j,0,2) tmp[i][j]=can[i][j];
		forn(i,1,n) forn(j,0,2) tmp[i][j]+=tmp[i-1][j];
		forn(j,0,2){
			cout<<"can["<<j<<"]: ";
			forn(i,0,n) cout<<tmp[i][j]<<" ";
			cout<<'\n';
		}
	}
	
	if(DEBUG) cout<<"rec("<<i<<","<<j<<"): end"<<'\n';
	if(DEBUG) cout<<'\n';
	return (dp[i][j] = ok);
}

string solve_puzzle(string s, vector<int> c_)
{
	mset(can,0); mset(pre,0); mset(dp,-1);
	c = c_;
	
	n = s.length();
	m = c.size();
	
	forn(i,0,n)
	{
		if(s[i]=='_') pre[i][0]++;
		if(s[i]=='X') pre[i][1]++;
		if(i){
			forn(j,0,2) pre[i][j]+=pre[i-1][j];
		}
	}
	
	for(int i=n-1;i>=0;i--)
	{
		if(check(i+1, n-1, 1)) continue;
		if(rec(i, m-1))
		{
			mark(i+1, n-1, 0);
		}
	}
	
	forn(i,1,n)
	{
		forn(j,0,2)
		{
			can[i][j] += can[i-1][j];
		}
	}
	
	string ans(n, '$');
	forn(i,0,n)
	{
		if(can[i][0] && can[i][1]) ans[i] = '?';
		else if(can[i][0]) ans[i] = '_';
		else if(can[i][1]) ans[i] = 'X';
		else {
			cout << "Impossible at i="<<i<<'\n';
		}
	}
	
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool rec(int, int)':
paint.cpp:67:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   67 |  if(i-c[j]+1 < 0) return (dp[i][j] = 0); if(DEBUG) SD(3);
      |  ^~
paint.cpp:67:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   67 |  if(i-c[j]+1 < 0) return (dp[i][j] = 0); if(DEBUG) SD(3);
      |                                          ^~
paint.cpp:68:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |  if(check(i-c[j]+1, i, 0)) return (dp[i][j] = 0); if(DEBUG) SD(4);
      |  ^~
paint.cpp:68:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |  if(check(i-c[j]+1, i, 0)) return (dp[i][j] = 0); if(DEBUG) SD(4);
      |                                                   ^~

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