Submission #363628

#	Time	Username	Problem	Language	Result	Execution time	Memory
363628		CSQ31	Paint By Numbers (IOI16_paint)	C++14	7 / 100	1 ms	364 KiB

paint

//#include "grader.cpp"
#include <cstdlib>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
std::string solve_puzzle(std::string s, std::vector<int> c){
	int n = sz(s);
	int k = sz(c);
	vector<vector<bool>>dpl(n+2,vector<bool>(k+1,0)),dpr(n+2,vector<bool>(k+1,0));
	vector<int>l(k+1,1e9),r(k+1);
	for(int i=0;i<n;i++){
		if(i){
			for(int j=0;j<k;j++){
				dpl[i][j]=dpl[i][j]|dpl[i-1][j];
			}
		}
		if(s[i] == '_')continue;
		for(int j=0;j<k;j++){
			if(!j || dpl[i][j-1]){
			    //we try to extend
			    bool ok = 1;
			    for(int e=0;e<c[j];e++){
					if(e+i >=n || s[e+i] == '-'){ok = 0;break;}
				}	
				if(ok){
					//cout<<i<<" "<<j<<" "<<i+c[j]<<" "<<n<<'\n';
					  if(i+c[j]<=n) dpl[i+c[j]][j] = 1;
					
				}
				
			}
		}
	}
	//for(int j=0;j<k;j++){
	//  for(int i=0;i<n;i++)cout<<dpl[i][j]<<" ";
	//  cout<<'\n';
   // }
	for(int i=n-1;i>=0;i--){
		if(i!=n-1){
			for(int j=0;j<k;j++){
				dpr[i][j] = dpr[i][j]|dpr[i+1][j];
			}
		}
		if(s[i] == '_')continue;
		for(int j=k-1;j>=0;j--){
			if(j == k-1 || dpr[i][j+1]){
			    //we try to extend
			    bool ok = 1;
			    for(int e=0;e<c[j];e++){
					if(i-e <0 || s[i-e] == '-'){ok = 0;break;}
				}	
				if(ok){
					if(i-c[j] >=0)dpr[i-c[j]][j] = 1;
				}
				
			}
		}
	}
	//for(int j=0;j<k;j++){
	//  for(int i=0;i<n;i++)cout<<dpr[i][j]<<" ";
	 // cout<<'\n';
   // }
    for(int i=0;i<=n;i++){
		for(int j=0;j<k;j++){
		   if(j == k-1 || dpr[i][k-j-1]){
			   if(dpl[i][j]){
			     l[j] = min(l[j],i-c[j]);
			     r[j] = max(r[j],i-1);	
			   }
		   }
		}
	}
	vector<int>cnt(2*n+1);
	string ans(n,'a');
	for(int i=0;i<k;i++){
		//cout<<r[i]-c[i]+1<<" "<<l[i]+c[i]-1<<'\n';
		//cout<<l[i]<<" "<<r[i]<<'\n';
		if(l[i] != 1e9){
		   cnt[l[i]]++;
		   cnt[r[i]+1]--;
			for(int j=max(0,r[i]-c[i]+1);j<l[i]+c[i];j++){
				assert(j>=0 && j<n);
				ans[j] = 'X';
			}
		}
	}
	for(int i=1;i<n;i++)cnt[i]+=cnt[i-1];
	for(int i=0;i<n;i++){
		if(cnt[i] && ans[i] == 'a')ans[i] = '?';
		else if(ans[i] == 'a')ans[i] = '_';
	}
	//cout<<ans<<'\n';
   // for(int i=0;i<k;i++)cout<<l[i]<<" "<<r[i]<<'\n';
    return ans;
}

• Subtask 1: 7 / 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