Submission #963197

#	Time	Username	Problem	Language	Result	Execution time	Memory
963197		ErJ	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	600 KiB

paint

    #include <bits/stdc++.h>
     
    using namespace std;
    #define ll long long
    #define vi vector<ll>
    #define pp pair<ll, ll>
    #define inf 1000000000000000000
    #define vvi vector<vi>
    #define vp vector<pp>
    #define vvp vector<vp>
    #define rep(i, n) for(int i = 0; i < n; i++)
    #define mod 1000000007
     
     
    vvi createDP(string s, vector<int> c) {
        vvi dp(s.size());
        vi pref_(s.size() + 1), prefX(s.size() + 1);
        pref_[0] = 0;
        prefX[0] = 0;
        rep(i, dp.size()) {
            pref_[i + 1] = pref_[i];
            prefX[i + 1] = prefX[i];
            if (s[i] == '_') pref_[i + 1]++;
            if (s[i] == 'X') prefX[i + 1]++;
            dp[i].resize(c.size() + 1);
            rep(j, dp[i].size()) {
                dp[i][j] = 0;
            }
            if (prefX[i + 1] == 0) dp[i][0] = 1;
            else dp[i][0] = 0;
     
        }
        dp[0][0] = 1;
        for (int i = 1; i < dp[0].size(); i++) {
            dp[0][i] = 0;
        }
        for (int i = 1; i < dp.size(); i++) {
            rep(j, dp[i].size()) {
                if (s[i] != 'X') {
                    dp[i][j] = dp[i - 1][j];
                }         
                if (j >= 1 && (i - c[j - 1] >= 0) && (pref_[i + 1] - pref_[i - c[j - 1] + 1] == 0)) {
                    if (j == 1) {
                        dp[i][j] = max(dp[i][j], dp[i - c[j - 1]][j - 1]);
                    }
                    else {
     
                        dp[i][j] = max(dp[i][j], dp[i - c[j - 1] - 1][j - 1]);
                    }
                }
            }
        }
        return dp;
    }
     
    string solve_puzzle(string s, vector<int> c) {
        s = "__" + s + "__";
        vi pref_(s.size() + 1), prefX(s.size() + 1);
        pref_[0] = 0;
        prefX[0] = 0;
        rep(i, s.size()) {
            pref_[i + 1] = pref_[i];
            prefX[i + 1] = prefX[i];
            if (s[i] == '_') pref_[i + 1]++;
            if (s[i] == 'X') prefX[i + 1]++;
        }
        
        vvi dp = createDP(s, c);
        string s2 = "";
        vector<int> c2;
        rep(i, s.size()) {
            s2 += s[s.size() - 1 -i];
        }
        rep(i, c.size()) {
            c2.push_back(c[c.size() - 1 - i]);
        }
        vvi dp2 = createDP(s2, c2);
     
     
        vi canX(dp.size()), can_(dp.size());
        for (int i = 1; i < dp.size() - 1; i++) {
            can_[i] = 0;
            canX[i] = 0;
            rep(j, dp[i].size()) {
                if (dp[i - 1][j] == 1 && dp2[dp2.size() - (i + 1) - 1][c.size() - j] == 1 && s[i] != 'X') {
                    can_[i] = 1;
                }
            }
        }
        rep(j, c.size()) {
            for (int i = 2; i < dp.size() - 2; i++) {
                ll start = i, end = i + c[j] - 1;
                if (end >= s.size()) continue;
                if (s[start - 1] != 'X' && s[end + 1] != 'X' && pref_[end + 1] - pref_[start - 1 + 1] == 0) {
                    if (end + 2 > dp.size() - 1) continue;
                    if (dp[start - 2][j] == 1 && dp2[dp2.size() - (end + 2) - 1][c.size() - 1 - j] == 1) {
                        canX[start]++;
                        canX[end + 1]--;
                    }
                }
            }
        }
        ll sumCanX = 0;
        rep(i, canX.size()) {
            sumCanX += canX[i];
            if (sumCanX > 0) {
                canX[i] = 1;
            }
            else {
                canX[i] = 0;
            }
        }
     
     
        string ans = "";
        for (int i = 2; i < dp.size() - 2; i++) {
            if (s[i] == '.') {
                if (canX[i] == 1 && can_[i] == 1) {
                    ans += '?';
                }
                else if (canX[i] == 1) {
                    ans += 'X';
                }
                else {
                    ans += '_';
                }
            }
            else {
                ans += s[i];
            }
        }
        return ans;
    }

Compilation message (stderr)

paint.cpp: In function 'std::vector<std::vector<long long int> > createDP(std::string, std::vector<int>)':
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   20 |         rep(i, dp.size()) {
      |             ~~~~~~~~~~~~                
paint.cpp:20:9: note: in expansion of macro 'rep'
   20 |         rep(i, dp.size()) {
      |         ^~~
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   26 |             rep(j, dp[i].size()) {
      |                 ~~~~~~~~~~~~~~~         
paint.cpp:26:13: note: in expansion of macro 'rep'
   26 |             rep(j, dp[i].size()) {
      |             ^~~
paint.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int i = 1; i < dp[0].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~
paint.cpp:37:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int i = 1; i < dp.size(); i++) {
      |                         ~~^~~~~~~~~~~
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   38 |             rep(j, dp[i].size()) {
      |                 ~~~~~~~~~~~~~~~         
paint.cpp:38:13: note: in expansion of macro 'rep'
   38 |             rep(j, dp[i].size()) {
      |             ^~~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   61 |         rep(i, s.size()) {
      |             ~~~~~~~~~~~                 
paint.cpp:61:9: note: in expansion of macro 'rep'
   61 |         rep(i, s.size()) {
      |         ^~~
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   71 |         rep(i, s.size()) {
      |             ~~~~~~~~~~~                 
paint.cpp:71:9: note: in expansion of macro 'rep'
   71 |         rep(i, s.size()) {
      |         ^~~
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   74 |         rep(i, c.size()) {
      |             ~~~~~~~~~~~                 
paint.cpp:74:9: note: in expansion of macro 'rep'
   74 |         rep(i, c.size()) {
      |         ^~~
paint.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i = 1; i < dp.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~~
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   84 |             rep(j, dp[i].size()) {
      |                 ~~~~~~~~~~~~~~~         
paint.cpp:84:13: note: in expansion of macro 'rep'
   84 |             rep(j, dp[i].size()) {
      |             ^~~
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
   90 |         rep(j, c.size()) {
      |             ~~~~~~~~~~~                 
paint.cpp:90:9: note: in expansion of macro 'rep'
   90 |         rep(j, c.size()) {
      |         ^~~
paint.cpp:91:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for (int i = 2; i < dp.size() - 2; i++) {
      |                             ~~^~~~~~~~~~~~~~~
paint.cpp:93:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 if (end >= s.size()) continue;
      |                     ~~~~^~~~~~~~~~~
paint.cpp:95:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |                     if (end + 2 > dp.size() - 1) continue;
      |                         ~~~~~~~~^~~~~~~~~~~~~~~
paint.cpp:11:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     #define rep(i, n) for(int i = 0; i < n; i++)
......
  104 |         rep(i, canX.size()) {
      |             ~~~~~~~~~~~~~~              
paint.cpp:104:9: note: in expansion of macro 'rep'
  104 |         rep(i, canX.size()) {
      |         ^~~
paint.cpp:116:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         for (int i = 2; i < dp.size() - 2; i++) {
      |                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10