이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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(k+1, 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(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;
}
컴파일 시 표준 에러 (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);
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |