제출 #724649

#제출 시각아이디문제언어결과실행 시간메모리
724649joelgun14Paint By Numbers (IOI16_paint)C++17
59 / 100
1 ms340 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; std::string solve_puzzle(std::string s, std::vector<int> c) { // dp O(NK) // nanti transisi coba dari i - 1 terus anggep // nanti cari semua previous states // bisa semacam dijkstra semua previous states/bfs // nanti previous state ada kemungkinan 0 atau 1? // yg dp[i][k] = 1 nanti jadiin yes terus nanti cari state sebelumnya dmn // find latest sm find earliest // nanti cek state boleh transisi kalo??? // dia statenya harus ambil sisanya int n = s.size(), k = c.size(); bool dp[n + 1][k + 1]; memset(dp, 0, sizeof(dp)); // bisa ambil coba ambil dr n - c[i], i - 1 atau n - 1, i // nanti case ambilnya bs coba dua"nya // case valid: s = " " + s; c.insert(c.begin(), 0); int prefa[n + 1], prefb[n + 1]; prefa[0] = prefb[0] = 0; prefb[0] = 1; for(int i = 1; i <= n; ++i) { prefa[i] = prefa[i - 1]; prefb[i] = 0; if(s[i] == '.') prefa[i]++, prefb[i]++; else if(s[i] == 'X') prefa[i]++; else prefb[i]++; } for(int i = 0; i <= n; ++i) { if(s[i] == 'X') break; dp[i][0] = 1; } for(int j = 1; j <= k; ++j) { for(int i = 1; i <= n; ++i) { //cout << i << " " << c[j] << " " << prefa[i] << " " << prefa[i - c[j]] << " " << prefb[i - c[j]] << " " << c[j] << endl; if(i >= c[j] && prefa[i] - prefa[i - c[j]] == c[j] && prefb[i - c[j]]) { //cout << "DEBUG " << i << " " << j << endl; //cout << i - c[j] << " " << j - 1 << endl; if(i == c[j]) dp[i][j] = dp[i - 1][j] | dp[i - c[j]][j - 1]; else dp[i][j] = dp[i - 1][j] | dp[i - c[j] - 1][j - 1]; } else if(s[i] != 'X') dp[i][j] = dp[i - 1][j]; //cout << dp[i][j] << " "; } //cout << endl; } // coba dr kemunculan X terakhir atau 0 // terus nanti cek dia bs dateng drmn aja // cek previousnya yg berlaku // nanti kalo misal bisa dr i - 1, j berarti sel sekarang itu white // kalo misal bs dr i - c[j], j - 1 berarti sel sekarang itu black bool white[n + 1], black[n + 1]; memset(white, 0, sizeof(white)); memset(black, 0, sizeof(black)); bool vis[n + 1][k + 1]; memset(vis, 0, sizeof(vis)); queue<pair<int, int>> q; vector<pair<int, bool>> bl; //cout << "TEST" << endl; int xidx = -1; for(int i = n; i >= 1; --i) { if(!dp[i][k]) break; if(s[i] == 'X') { xidx = i; break; } } if(xidx == -1) { for(int i = n; i >= 1; --i) { if(!dp[i][k]) break; q.push({i, k}); } } else { for(int i = xidx; i <= min(xidx + c.back() - 1, n); ++i) { if(dp[i][k]) q.push({i, k}); } } while(q.size()) { int x = q.front().first, y = q.front().second; q.pop(); if(x < 0 || y < 0 || vis[x][y] || !dp[x][y]) continue; vis[x][y] = 1; if(x != 0 && dp[x - 1][y] && s[x] != 'X') { //cout << x << " " << y << endl; white[x] = 1, q.push({x - 1, y}); } if(y != 0 && x >= c[y] && prefa[x] - prefa[x - c[y]] == c[y] && prefb[x - c[y]] && dp[max(0, x - c[y] - 1)][y - 1]) { //cout << x << " " << y << endl; // antara x - c[y] sampai x jadiin black bl.push_back({x - c[y] + 1, 0}), bl.push_back({x, 1}), q.push({x - c[y] - 1, y - 1}); //cout << x << " " << y << endl; white[x - c[y]] = 1; } } sort(bl.begin(), bl.end()); int idx = 0, cnt = 0; for(int i = 1; i <= n; ++i) { //cout << "TEST" << endl; while(idx < bl.size() && bl[idx].first == i) { if(cnt > 0) black[i] = 1; if(bl[idx].second) --cnt; else ++cnt; if(cnt > 0) black[i] = 1; ++idx; } //cout << "TEST2" << endl; if(cnt > 0) black[i] = 1; } string ret = ""; for(int i = 1; i <= n; ++i) { if(white[i] && black[i]) ret += '?'; else if(black[i]) ret += 'X'; else ret += '_'; } return ret; }

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:116:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |         while(idx < bl.size() && bl[idx].first == 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...