제출 #1199052

#제출 시각아이디문제언어결과실행 시간메모리
1199052BigBadBullySprinklers (CEOI24_sprinklers)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define pid pair<int,double> #define pii pair<int,int> #define ff first #define ss second const int inf = 1e18; const int maxn = 1e3; using namespace std; void solve() { int n,m; cin >> n >> m; vector<int> va(n),vb(m); for (int i = 0; i < n; i++) cin >> va[i]; for (int i = 0; i < m; i++) cin >> vb[i]; set<int> svn; for (int x: va) svn.insert(x); vector<int> nvb; for (int i = 0; i < m; i++) if (!svn.count(vb[i])) nvb.push_back(vb[i]); //1 = R //0 = L m = nvb.size(); vb = nvb; string bad = "l"; auto calc = [&](int k) { vector<vector<pii>> seg(n); for (int i = 0; i < m; i++) { vector<int> mask; auto it2 = upper_bound(va.begin(),va.end(),vb[i]+k)-va.begin(); auto it0 = lower_bound(va.begin(),va.end(),vb[i]-k)-va.begin(); auto it1 = lower_bound(va.begin(),va.end(),vb[i])-va.begin(); if (it0 >= n ||it2 == 0) return 0; for (int j = it0; j < it1; j++) mask.push_back(0); for (int j = it1; j < it2; j++) mask.push_back(1); if (count(mask.begin(),mask.end(),0) >= 3) seg[it2-1].push_back({3,0}); else if (count(mask.begin(),mask.end(),1) >= 3) seg[it2-1].push_back({3,(1<<3)-1}); else { int sum = 0; int f = mask.size(); for (int j = 0; j < f; j++) sum+=(1<<f-1-j)*mask[j]; seg[it2-1].push_back({mask.size(),sum}); } } array<int,8> prev,nxt; for (int i = 0; i < 8; i++) prev[i] = 0; vector<array<int,8>> dp(n); for (int i = 0; i < n; i++) { array<int,16> cands; for (int j = 0; j < 8; j++) cands[2*j] = (prev[j] != -1 ? j : -1), cands[2*j+1] = (prev[j] != -1 ? j : -1); for (auto x : seg[i]) for (int cnt = 0; cnt < 16; cnt+=(1<<x.ff)) cands[x.ss+cnt] = -1; for (int j = 0; j < 8; j++) prev[j]=(cands[j] != -1 ? cands[j] : cands[j+(1<<3)]); dp[i] = prev; } /* for (int j = 0; j < 8; j++) if (prev[j] != -1) { string ans; auto cur = j; for (int i = n-1; i >= 0; i--) ans.push_back(cur%2 ? 'R' : 'L'),cur = dp[i][cur]; reverse(ans.begin(),ans.end()); return ans; } */ for (int j = 0; j < 8; j++) if (prev[j]!=1) return 1; return 0; }; auto calc_s = [&](int k) { vector<vector<pii>> seg(n); for (int i = 0; i < m; i++) { vector<int> mask; auto it2 = upper_bound(va.begin(),va.end(),vb[i]+k)-va.begin(); auto it0 = lower_bound(va.begin(),va.end(),vb[i]-k)-va.begin(); auto it1 = lower_bound(va.begin(),va.end(),vb[i])-va.begin(); for (int j = it0; j < it1; j++) mask.push_back(0); for (int j = it1; j < it2; j++) mask.push_back(1); if (count(mask.begin(),mask.end(),0) >= 3) seg[it2-1].push_back({3,0}); else if (count(mask.begin(),mask.end(),1) >= 3) seg[it2-1].push_back({3,(1<<3)-1}); else { int sum = 0; int f = mask.size(); for (int j = 0; j < f; j++) sum+=(1<<f-1-j)*mask[j]; seg[it2-1].push_back({mask.size(),sum}); } } array<int,8> prev,nxt; for (int i = 0; i < 8; i++) prev[i] = 0; vector<array<int,8>> dp(n); for (int i = 0; i < n; i++) { array<int,16> cands; for (int j = 0; j < 8; j++) cands[2*j] = (prev[j] != -1 ? j : -1), cands[2*j+1] = (prev[j] != -1 ? j : -1); for (auto x : seg[i]) for (int cnt = 0; cnt < 16; cnt+=(1<<x.ff)) cands[x.ss+cnt] = -1; for (int j = 0; j < 8; j++) prev[j]=(cands[j] != -1 ? cands[j] : cands[j+(1<<3)]); dp[i] = prev; } for (int j = 0; j < 8; j++) if (prev[j] != -1) { string ans; auto cur = j; for (int i = n-1; i >= 0; i--) ans.push_back(cur%2 ? 'R' : 'L'),cur = dp[i][cur]; reverse(ans.begin(),ans.end()); return ans; } return 0; }; if (m==0) { cout << 0 <<'\n'; cout << string(n,'L') << '\n'; return; } int l = 0, r = 1e9; while(r-l) { int mid =l+r>>1; if (calc(mid)) r = mid; else l = mid+1; } if (l==1e9) cout << -1 << endl; else cout << l << '\n' << calc_s(l) << '\n'; } signed main() { ios::sync_with_stdio(0); int t = 1; //cin >> t; while(t--) solve(); }

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

Main.cpp:9:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const int inf = 1e18;
      |                 ^~~~
Main.cpp: In lambda function:
Main.cpp:155:16: error: inconsistent types 'std::__cxx11::basic_string<char>' and 'int' deduced for lambda return type
  155 |         return 0;
      |                ^