Submission #139918

#TimeUsernameProblemLanguageResultExecution timeMemory
139918SirCenessPaint By Numbers (IOI16_paint)C++14
80 / 100
6 ms504 KiB
#include "paint.h" #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define inside sl<=l&&r<=sr #define outside r<sl||sr<l #define orta ((l+r)>>1) #define INF 1000000009 #define mod 1000000007 #define ppair(x); cerr << "(" << x.first << ", " << x.second << ")\n"; #define bas(x) #x << ": " << x << " " #define prarr(x, n); cerr << #x << ": "; for(int qsd = 0; qsd < n; qsd++) cerr << x[qsd] << " "; cerr << "\n"; #define prarrv(x); cerr << #x << ": "; for(int qsd = 0; qsd < (int)x.size(); qsd++) cerr << x[qsd] << " "; cerr << "\n"; using namespace std; typedef long long ll; string s; int pre[101]; int prex[101]; string ans; vector<int> c; vector<int> xarr; int dp[200005][101]; int varmi(int l, int r){ int ans = 0; if (l == 0) ans = pre[r]; else ans = pre[r] - pre[l-1]; if (ans > 0) return 1; else return 0; } int varmix(int l, int r){ int ans = 0; if (l == 0) ans = pre[r]; else ans = pre[r] - pre[l-1]; if (ans > 0) return 1; else return 0; } void merge(int i, char c){ if (ans[i] == '!') ans[i] = c; else if (ans[i] == '_' && c == 'X') ans[i] = '?'; else if (ans[i] == 'X' && c == '_') ans[i] = '?'; else if (ans[i] == '_' && c == '?') ans[i] = '?'; else if (ans[i] == 'X' && c == '?') ans[i] = '?'; } vector<int> subv(int l, int r, vector<int>& arr){ vector<int> ans; for (int i = l; i <= r; i++) ans.pb(arr[i]); return ans; } void update(int l, int r){ xarr[l]++; if (r+1 < s.size()) xarr[r+1]--; } int f(int i, int k){ //cout << "f(" << i << ", " << k << ")" << endl; if (i >= s.size()) return (k == c.size()); if (dp[i][k] != -1) return dp[i][k]; int ans = 0; if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0; if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){ ans = f(i+c[k]+1, k+1); if (ans){ update(i, i+c[k]-1); merge(i+c[k], '_'); } } int ans2 = 0; if (s[i] != 'X') ans2 = f(i+1, k); if (ans2) merge(i, '_'); return dp[i][k] = (ans|ans2); } string solve_puzzle(string S, vector<int> C) { c = C; s = S; int sum = 0; int sumx = 0; for (int i = 0; i < s.size(); i++){ if (s[i] == '_') sum++; pre[i] = sum; if (s[i] == 'X') sumx++; prex[i] = sumx; } ans = ""; for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!'); //for (int i = 0; i < s.size(); i++) if (s[i] == 'X') ans[i] = 'X'; xarr.resize(s.size()); for (int i = 0; i < s.size(); i++) xarr[i] = 0; for (int i = 0; i <= s.size()+1; i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1; f(0, 0); if (xarr[0] > 0) merge(0, 'X'); for (int i = 1; i < s.size(); i++){ xarr[i] += xarr[i-1]; if (xarr[i] > 0) merge(i, 'X'); } return ans; }

Compilation message (stderr)

paint.cpp: In function 'void update(int, int)':
paint.cpp:60:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (r+1 < s.size()) xarr[r+1]--;
      ~~~~^~~~~~~~~~
paint.cpp: In function 'int f(int, int)':
paint.cpp:65:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= s.size()) return (k == c.size());
      ~~^~~~~~~~~~~
paint.cpp:65:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (i >= s.size()) return (k == c.size());
                             ~~^~~~~~~~~~~
paint.cpp:68:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0; 
      ~~^~~~~~~~~~~
paint.cpp:68:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k != c.size() && i+c[k] > s.size()) return dp[i][k] = 0; 
                       ~~~~~~~^~~~~~~~~~
paint.cpp:69:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
      ~~^~~~~~~~~~
paint.cpp:69:59: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (k < c.size() && (varmi(i, c[k]+i-1) == 0) && (c[k]+i == s.size() || s[i+c[k]] != 'X')){
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++){
                  ~~^~~~~~~~~~
paint.cpp:94:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) ans += (s[i] == '_' ? '_' : '!');
                  ~~^~~~~~~~~~
paint.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) xarr[i] = 0;
                  ~~^~~~~~~~~~
paint.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= s.size()+1; i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
                  ~~^~~~~~~~~~~~~
paint.cpp:100:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= s.size()+1; i++) for (int j = 0; j <= c.size(); j++) dp[i][j] = -1;
                                                        ~~^~~~~~~~~~~
paint.cpp:105:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.size(); i++){
                  ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...