제출 #567101

#제출 시각아이디문제언어결과실행 시간메모리
567101Belgutei벽 칠하기 (APIO20_paint)C++17
28 / 100
94 ms16704 KiB
#include "paint.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second #define pb push_back #define mk make_pair #define X real() #define Y imag() #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define MOD 1000000007 #define MOD1 1000000009 #define sqr(x) sqr((x)*(x)) void debug_out() { cerr << endl; } template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); } #ifdef BE_DEBUG #define debug(...) cerr << "\033[1;31m(" << #__VA_ARGS__ << "):\033[0m", debug_out(__VA_ARGS__) #else #define debug(...) #endif map<int,bool> mp[100005]; map<ll,bool> mm; int dp[1005]; vector<int> v[30]; int l,r; int mn; int z[30]; int level; void dfs(int k, int x) { int yy = z[level-k] * x; int zz = z[level-k] * (x + 1) - 1; if(l <= yy && zz <= r) { mn = min (mn,v[k][x]); return; } if(zz < l || yy > r || k == level) return; dfs(k + 1, x * 2); dfs(k + 1, x * 2 + 1); } void update(int pos, int val) { v[level][pos] = val; for(int i = level - 1; i >= 0; i --) { pos/=2; v[i][pos] = min(v[i + 1][pos * 2],v[i + 1][pos * 2 + 1]); } } int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { bool sub_1 = 0; for(int i = 0; i < B.size(); i ++) { if(B[i].size() > 1) sub_1 = 1; } if(sub_1 == 0) { // subtask 1 ll zereg[N + 5]; zereg[0] = 1; for(int i = 1; i <= N; i ++) { zereg[i] = (zereg[i - 1] * 10) % MOD; } // ll hash_val[M + 5]; hash_val[0] = 0; for(int i = 0; i < M; i ++) { hash_val[0] = (hash_val[0] * 10 + B[i][0]) % MOD; } for(int i = 0; i < M; i ++) { hash_val[i + 1] = ((hash_val[i] - (B[i][0] * zereg[M - 1]) % MOD + MOD) % MOD * 10 + B[i][0]) % MOD; } for(int i = 0; i < M; i ++) { mm[hash_val[i]] = 1; debug(hash_val[i]); } // z[0] = 1; for(int i = 0; i < 30; i ++) { if(z[i] >= N) { level = i; break; } z[i + 1] = z[i] * 2; } for(int i = 0; i <= level; i ++) { for(int j = 0; j < z[i]; j ++) { v[i].pb(1e9 + 7); } } // ll h[N + 5]; for(int i = 0; i < N; i ++) { if(i == 0) h[i] = C[i]; else { h[i] = (h[i - 1] * 10 + C[i]) % MOD; } debug(h[i]); } // for(int i = M - 1; i < N; i ++) { ll cur_hash = h[i]; if(i != M - 1) { cur_hash = (h[i] - (h[i - M] * zereg[M]) % MOD + MOD) % MOD; } debug(cur_hash); if(mm[cur_hash] == 1) { //debug("WTF"); if(i == M - 1) { update(i,1); continue; } l = i - M; r = i - 1; debug(i); //cout << l << ' ' << r << '\n'; mn = 1e9 + 7; dfs(0,0); update(i,mn + 1); } } /* for(int i = 0; i<= level; i ++) { for(int j = 0; j < v[i].size(); j ++) { cout << v[i][j] << ' '; } cout << '\n'; } */ if(v[level][N - 1] >= 1e9) { return -1; } return v[level][N - 1]; } for(int i = 0; i < B.size(); i ++) { for(int j = 0; j < B[i].size(); j ++) { mp[i][B[i][j]] = 1; } } for(int i = M - 1; i < N; i ++) { int l = i - M + 1; int r = i; int starter = 0; bool check = 0; while(starter < M) { int cur = starter; bool ok = 0; for(int j = l; j <= r; j ++) { if(mp[cur][C[j]] == 0) { ok = 1; break; } cur ++; if(cur == M) cur = 0; } if(ok == 0) { check = 1; break; } starter ++; } if(check == 0) { continue; } if(i == M - 1) { dp[i] = 1; continue; } int mn = 1e9; for(int j = i - 1; j >= i - M; j --) { if(dp[j] == 0) continue; mn = min(mn,dp[j]); } if(mn != 1e9) { mn ++; dp[i] = mn; } } if(dp[N - 1] == 0) return -1; return dp[N - 1]; }

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

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i = 0; i < B.size(); i ++) {
      |                    ~~^~~~~~~~~~
paint.cpp:143:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |     for(int i = 0; i < B.size(); i ++) {
      |                    ~~^~~~~~~~~~
paint.cpp:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(int j = 0; j < B[i].size(); j ++) {
      |                        ~~^~~~~~~~~~~~~
#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...