Submission #285283

#	Time	Username	Problem	Language	Result	Execution time	Memory
285283		Shafin666	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	512 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<ll, ll>
#define nyan "(=^･ω･^=)"
#define read_input         freopen("in.txt","r", stdin)
#define print_output       freopen("out.txt","w", stdout)
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 2e5+10;
int dash[maxn];
int notx[maxn], noty[maxn];
int lft[maxn], rgt[maxn];

std::string solve_puzzle(std::string s, std::vector<int> c) {
    int n = s.length();
    int k = c.size();

    for(int i = 0; i < n; i++) dash[i] = s[i] == '_';
    for(int i = 1; i < n; i++) dash[i] += dash[i-1];

    for(int i = 0, j = 0; i < n && j < k; i++) {
    	int cnt = dash[i + c[j] - 1] - (i? dash[i-1] : 0);

    	if(!cnt) lft[i + c[j] - 1]++, i += c[j++];
    }

    for(int i = n-1, j = k-1; i >= 0 && j >= 0; i--) {
    	int cnt = dash[i] - ((i < c[j])? 0 : dash[i - c[j]]);

    	if(!cnt) rgt[i - c[j] + 1]++, i -= c[j--];
    }

    for(int i = 0; i < n; i++) lft[i] += lft[i-1];
    for(int i = n-1; i >= 0; i--) rgt[i] += rgt[i+1];

    for(int i = 0; i < n; i++) {
    	int now = rgt[i+1] + (i? lft[i-1] : 0);
    	notx[i] = (now >= k);
    }

    noty[0] = 1; noty[n-1] = 1;
    for(int i = 1; i < n-1; i++) {
    	noty[i] = notx[i+1] | notx[i-1];
    }

    // for(int i = 0; i < n; i++) cout << lft[i] << " "; cout << endl;
    // for(int i = 0; i < n; i++) cout << rgt[i] << " "; cout << endl;

    // cout << endl;
    // for(int i = 0; i < n; i++) cout << notx[i] << " "; cout << endl;
    // for(int i = 0; i < n; i++) cout << noty[i] << " "; cout << endl;

    string ret;
	for(int i = 0; i < n; i++) {
		if(notx[i] && noty[i]) ret += "?";
		else if(notx[i]) ret += "_";
		else if(noty[i]) ret += "X";
		else ret += "X";
	}

    return ret;
}

• 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