제출 #1158438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1158438		omtheprogrammer1	Paint By Numbers (IOI16_paint)	C++20	0 / 100	0 ms	320 KiB

paint

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

using namespace std;

#define endl "\n"
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define mp make_pair
#define pb push_back
#define fix(prec) {cout << setprecision(prec) << fixed;}
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define ins insert
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define sz(v) (ll)v.size()
#define readgraph(list, edges) for (ll i = 0; i < edges; i++) {ll a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define F_OR(i, a, b, s) for (ll i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

ll prexor(ll i) {
  i++;
  if ((i % 4) == 0) return 0;
  else if ((i % 4) == 1) return i - 1;
  else if ((i % 4) == 2) return 1;
  else return i;
}
ll rangexor(ll l, ll r) {
  if (l == 0) return prexor(r);
  return prexor(r)^prexor(l - 1);
}
ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  while (lb < rb) {
    ll mb = (lb + rb) / 2;
    f(mb) ? rb = mb : lb = mb + 1;
  }
  return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
  while (lb < rb) {
    ll mb = (lb + rb + 1) / 2;
    f(mb) ? lb = mb : rb = mb - 1;
  }
  return lb;
}

template<class A> void read(vector<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) {
  cin >> x;
}
void read(double& d) {
  string t;
  read(t);
  d = stod(t);
}
void read(long double& d) {
  string t;
  read(t);
  d = stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
  read(h);
  read(t...);
}
template<class A> void read(vector<A>& x) {
  EACH(a, x)
  read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
  EACH(a, x)
  read(a);
}

// #define cerr cout

mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b) {
  return uniform_int_distribution<ll>(a, b)(mt_rng);
}
/*--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------*/

const lld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
const ll INF = 1e17;
const int d4i[4] = { -1, 0, 1, 0}, d4j[4] = {0, 1, 0, -1};
const int d8i[8] = { -1, -1, 0, 1, 1, 1, 0, -1}, d8j[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int kni[8] = { +2, +2, -2, -2, 1, -1, 1, -1}, knj[8] = {1, -1, 1, -1, 2, 2, -2, -2};

int n, m, k, q, l, r, x, y, z , h;
const int tas = 2e5 + 10;
int a[tas];
int ca[tas];
int cb[tas];
int dp[tas][102];
int rdp[tas][102];
int rd1[102];
int prex[tas];
int prew[tas];
string s, t;
// vector<int> grid[tas];
// vector<pii> edges[tas];
int ans = 0;

void add(int l, int r) {
  cb[r + 1] += -1;
  cb[l] += 1;
}

void keep(int i, int j, int val) {
  if (i < -1) return;
  if (i >= 0) rdp[i][j] |= val;
  else {
    rd1[j] |= val;
  }
}

bool checkx(int l, int r) {
  // debug(l, r)
  return ((prex[r] - (l ? prex[l - 1] : 0)) == 0);
}

bool checkw(int l, int r) {
  // debug(l, r)
  return ((prew[r] - (l ? prew[l - 1] : 0)) == 0);
}

int get(int i, int j) {
  // debug(i, j)
  // return 1;
  if (i == -1) {
    return rd1[j];
  }
  else {
    return rdp[i][j];
  }
}

string solve_puzzle(string s, vector<int> c) {
  n = sz(s);
  k = sz(c);
  string ans;
  // debug(n)
  FOR(n) prex[i] = (s[i] == 'X');
  FOR(n) prew[i] = (s[i] == '_');
  FOR(i, 1, n) prew[i] += prew[i - 1], prex[i] += prex[i - 1];
  FOR(n + 1) FOR(j, 0, k + 1) dp[i][j] = 0;
  dp[0][0] = 1;
  FOR(n) FOR(j, 0, k + 1) {
    // debug(i, j, dp[i][j])
    if (s[i] != 'X') {
      dp[i + 1][j] |= dp[i][j];
    }
    if (s[i] != '_') {
      if (j != k && (i + c[j]) <= n && checkw(i, i + c[j] - 1)) {
        bool can = 1;
        if (i + c[j] < n) can &= checkx(i + c[j], i + c[j]);
        if (can) {
          dp[i + c[j] + 1][j + 1] |= dp[i][j];
        }
      }
    }
  }
  FOR(n + 1) FOR(j, 0, k + 1) rdp[i][j] = 0;
  rdp[n - 1][k] = 1;
  FOR(i, n - 1, -1, -1) FOR(j, 0, k + 1) {
    if (s[i] != 'X') {
      keep(i - 1, j, rdp[i][j]);
    }
    if (s[i] != '_') {
      if (j != 0 && (i - c[j - 1]) >= -1 && checkw(i, i - c[j - 1] + 1)) {
        bool can = 1;
        if (i - c[j - 1] >= 0)can &= checkx(i - c[j - 1], i - c[j - 1]);
        if (can) keep(i - c[j - 1] - 1, j - 1, rdp[i][j]);
      }
    }
  }
  // debug(get(n - 2, 0))
  FOR(n) {
    if (s[i] == '.') {
      FOR(j, 0, k) {
        ca[i] |= dp[i + 1][j + 1] & get(i - 1, j + 1);
        // if (i == 5) {
        //   debug(dp[i + 1][j + 1], get(i - 1, j + 1))
        // }
      }
      // debug(ca[n - 1])
      // debug(i, ca[i])
    }
  }
  FOR(k) {
    for (int l = 0; l + c[i] <= n; l++) {
      // debug(l + c[i] - 1)
      if (dp[l][i] && get(l + c[i] - 1, i + 1) && checkw(l, l + c[i] - 1)) {
        add(l, l + c[i] - 1);
      }
    }
  }
  FOR(i, 1, n) {
    // debug(i)
    cb[i] += cb[i - 1];
  }
  FOR(n) {
    // debug(i)
    if (s[i] != '.') {
      ans += s[i];
    }
    else {
      // debug(i)
      // debug(i, ca[i], cb[i])
      if (ca[i] && cb[i]) ans += "?";
      else if (ca[i]) ans += "_";
      else if (cb[i]) ans += "X";
    }
  }
  return ans;
}

// void solve(int tc = 0) {

//   cin >> k;
//   vector<int> vec;
//   FOR(k) cin >> a[i], vec.pb(a[i]);
//   cin >> s;
//   // debug(s)
//   cout << solve_puzzle(s, vec) << endl;;
// }


// int main() {
//   fastio

// #ifdef LOCAL
//   auto begin = std::chrono::high_resolution_clock::now();
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
//   freopen("error.txt", "w", stderr);
// #endif

//   ll tc = 1;
//   // cin >> tc;
//   for (int t = 0; t < tc; t++) solve(t);
// #ifdef LOCAL
//   auto end = std::chrono::high_resolution_clock::now();
//   auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
//   // cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
// #endif
// }

컴파일 시 표준 에러 (stderr) 메시지

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

• 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