Submission #963196

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963196	2024-04-14T17:21:53 Z	ErJ	Paint By Numbers (IOI16_paint)	C++17	Compilation error	0 ms	0 KB

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_puzzles(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

paint.cpp: In function 'std::vector<std::vector<long long int> > createDP(std::string, std::vector<int>)':
paint.cpp:11:36: 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:5: note: in expansion of macro 'rep'
   20 |     rep(i, dp.size()) {
      |     ^~~
paint.cpp:11:36: 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:9: note: in expansion of macro 'rep'
   26 |         rep(j, dp[i].size()) {
      |         ^~~
paint.cpp:34:23: 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:23: 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:36: 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:9: note: in expansion of macro 'rep'
   38 |         rep(j, dp[i].size()) {
      |         ^~~
paint.cpp: In function 'std::string solve_puzzles(std::string, std::vector<int>)':
paint.cpp:11:36: 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:5: note: in expansion of macro 'rep'
   61 |     rep(i, s.size()) {
      |     ^~~
paint.cpp:11:36: 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:5: note: in expansion of macro 'rep'
   71 |     rep(i, s.size()) {
      |     ^~~
paint.cpp:11:36: 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:5: note: in expansion of macro 'rep'
   74 |     rep(i, c.size()) {
      |     ^~~
paint.cpp:81:23: 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:36: 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:9: note: in expansion of macro 'rep'
   84 |         rep(j, dp[i].size()) {
      |         ^~~
paint.cpp:11:36: 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:5: note: in expansion of macro 'rep'
   90 |     rep(j, c.size()) {
      |     ^~~
paint.cpp:91: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]
   91 |         for (int i = 2; i < dp.size() - 2; i++) {
      |                         ~~^~~~~~~~~~~~~~~
paint.cpp:93:21: 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:29: 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:36: 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:5: note: in expansion of macro 'rep'
  104 |     rep(i, canX.size()) {
      |     ^~~
paint.cpp:116:23: 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++) {
      |                     ~~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cchxhApy.o: in function `main':
grader.cpp:(.text.startup+0x20b): undefined reference to `solve_puzzle(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status