Submission #334277

#TimeUsernameProblemLanguageResultExecution timeMemory
334277SwanPaint By Numbers (IOI16_paint)C++14
59 / 100
1 ms384 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 3; const int maxk = 101; bitset<maxk> pref[maxn]; bitset<maxk> suf[maxn]; int prefSum[maxn]; int prefSumBlack[maxn]; int isWhiteGood[maxn]; string ans; int n; int k; void addWhite(int l, int r){ isWhiteGood[l]++; isWhiteGood[r + 1]--; } int getSum(int l, int r){ int res = prefSum[r]; if(l)res-=prefSum[l - 1]; return res; } int getSumBlack(int l, int r){ int res = prefSumBlack[r]; if(l)res-=prefSumBlack[l - 1]; return res; } bool canSuf(int sufNum, int need){ if(sufNum == n){ if(need == k)return 1; else return 0; } if(need == k){ if(sufNum >= n)return 1; int sufSum = getSumBlack(sufNum, n - 1); if(sufSum)return 0; else return 1; } if(sufNum >= n)return 0; return suf[sufNum][need]; } bool canPref(int prefNum, int need){ if(prefNum == -1){ if(need == 0)return 1; else return 0; } if(need == 0){ if(prefNum <= -1)return 1; int prefSum = getSumBlack(0, prefNum); if(prefSum)return 0; else return 1; } if(prefNum < 0)return 0; return pref[prefNum][need - 1]; } void solveBlack(string& s, string& ans){ for(int i = 0; i < s.size();i++){ if(s[i] != '.')continue; bool can = 0; for(int prefCnt = 0; prefCnt<= k;prefCnt++){ int sufCnt = prefCnt; if(canPref(i - 1, prefCnt) && canSuf(i + 1, sufCnt)){ can = 1; } } if(!can){ ans[i] = 'X'; } } } bool putBlock(int l, int r, int j, string& s){ if(l){ if(s[l - 1] == 'X')return 0; } if(r != s.size() - 1){ if(s[r + 1] == 'X')return 0; } //cout << "MDA " << l << ' ' << r << ' ' << j << ' ' << canPref(l - 2, j) << ' ' << canSuf(r + 2, j + 1) << endl; return ((canPref(l - 2, j) && canSuf(r + 2, j + 1))); } void solveWhite(string& s, vector<int>& c, string& ans){ for(int j = 0; j < c.size();j++){ for(int l = 0 ; l < s.size();l++){ int r = l + c[j] - 1; if(r >= s.size())continue; if(getSum(l, r))continue; if(putBlock(l, r, j, s)){ addWhite(l, r); //cout << "OPA " << l << ' ' << r << endl; } } } int nowSum = 0; for(int i = 0; i < n;i++){ nowSum+=isWhiteGood[i]; if(s[i] != '.')continue; //cout << i << ' ' << nowSum << endl; if(nowSum == 0){ ans[i] = '_'; } } } void calc_suf(vector<int>& c, string& s){ for(int i = s.size() - 1; i >= 0;i--){ for(int j = c.size() - 1; j >= 0;j--){ if(s[j] != 'X' && i != s.size() - 1)suf[i][j] = suf[i + 1][j]; int r = i + c[j] - 1; if(r >= s.size())continue; int sumOnSegm = getSum(i, r); if(sumOnSegm)continue; //cout << i << ' ' << j << endl; if(j == c.size() - 1){ if(r == s.size() - 1){ suf[i][j] = 1; }else{ if(getSumBlack(r + 1, s.size() - 1)!=0)continue; else suf[i][j] = 1; } }else{ if(s[r + 1] == 'X')continue; if(r + 2 < s.size()){ if(suf[r + 2][j + 1]){ suf[i][j] = 1; } } } } } } void calc_pref(vector<int>& c, string& s){ for(int i = 0; i < s.size();i++){ for(int j = 0; j < c.size();j++){ if(s[j] != 'X' && i)pref[i][j] = pref[i - 1][j]; int l = i - c[j] + 1; if(l < 0)continue; int sumOnSegm = getSum(l, i); if(sumOnSegm)continue; if(j == 0){ if(l == 0){ pref[i][j] = 1; }else{ if(prefSumBlack[l - 1] != 0)continue; else pref[i][j] = 1; } }else{ if(s[l - 1] == 'X')continue; if(l - 2 >= 0){ if(pref[l - 2][j - 1]){ pref[i][j] = 1; } } } } } } string solve_puzzle(string s, vector<int> c) { n = s.size(); k = c.size(); for(int i = 0; i < s.size();i++){ if(s[i] == '_'){ prefSum[i]++; } if(s[i] == 'X'){ prefSumBlack[i]++; } if(s[i] != '.'){ ans+= s[i]; }else{ ans+='?'; } if(i){ prefSum[i] += prefSum[i - 1]; prefSumBlack[i] += prefSumBlack[i - 1]; } } calc_pref(c, s); calc_suf(c, s); solveBlack(s, ans); solveWhite(s, c, ans); // for(int i = 0; i < n;i++){ // cout << i << endl; // for(int j = 0; j <= k;j++){ // cout << suf[i][j] << ' '; // } // cout << endl; // } return ans; }

Compilation message (stderr)

paint.cpp: In function 'void solveBlack(std::string&, std::string&)':
paint.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < s.size();i++){
      |                    ~~^~~~~~~~~~
paint.cpp: In function 'bool putBlock(int, int, int, std::string&)':
paint.cpp:86:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     if(r != s.size() - 1){
      |        ~~^~~~~~~~~~~~~~~
paint.cpp: In function 'void solveWhite(std::string&, std::vector<int>&, std::string&)':
paint.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int j = 0; j < c.size();j++){
      |                    ~~^~~~~~~~~~
paint.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int l = 0 ; l < s.size();l++){
      |                         ~~^~~~~~~~~~
paint.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             if(r >= s.size())continue;
      |                ~~^~~~~~~~~~~
paint.cpp: In function 'void calc_suf(std::vector<int>&, std::string&)':
paint.cpp:119:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             if(s[j] != 'X' && i != s.size() - 1)suf[i][j] = suf[i + 1][j];
      |                               ~~^~~~~~~~~~~~~~~
paint.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |             if(r >= s.size())continue;
      |                ~~^~~~~~~~~~~
paint.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             if(j == c.size() - 1){
      |                ~~^~~~~~~~~~~~~~~
paint.cpp:126:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |                 if(r == s.size() - 1){
      |                    ~~^~~~~~~~~~~~~~~
paint.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |                 if(r + 2 < s.size()){
      |                    ~~~~~~^~~~~~~~~~
paint.cpp: In function 'void calc_pref(std::vector<int>&, std::string&)':
paint.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     for(int i = 0; i < s.size();i++){
      |                    ~~^~~~~~~~~~
paint.cpp:147:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         for(int j = 0; j < c.size();j++){
      |                        ~~^~~~~~~~~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:175:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for(int i = 0; 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...