제출 #1196298

#제출 시각아이디문제언어결과실행 시간메모리
1196298LGQ_A3K25Cultivation (JOI17_cultivation)C++20
컴파일 에러
0 ms0 KiB
#pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespace std; #define ll long long #define db double #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a*b / __gcd(a,b) #define I first #define II second #define pb push_back #define ii pair<int,int> const int INF = 2e9; const int N = 6e2 + 5; const int MOD = 1e9 + 7; int n, m, k; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); ll Rand(ll l,ll r) { return l+abs(rd()*1ll*rd())%(r-l+1); } namespace sub3 { int tg[N], num[N]; ll ans = 1e18; ii p[N]; array<int, 3> cur[N], f[N][N]; // L, R, M struct DQ { deque<ii> q; inline void add(ii x) { while (q.size() && q.back().I <= x.I) q.pop_back(); q.pb(x); } inline void del(int& x) { while (q.size() && q.front().II <= x) q.pop_front(); } inline int get() { if (q.empty()) return INF; else return q.front().I; } } L, R, M; inline void init() { for (int l = 1; l <= k; l++) { int sz = 0; for (int r = l; r <= k; r++) { int mx = p[r].II; for (int i = 1; i <= sz; i++) if (mx < tg[i]) swap(tg[i], mx); tg[++sz] = mx; f[l][r][0] = tg[1] - 1; f[l][r][1] = m - tg[sz]; for (int i = 1; i < sz; i++) f[l][r][2] = max(f[l][r][2], tg[i + 1] - tg[i] - 1); // cout << l << ' ' << r << ' ' << f[l][r][0] << ' ' << f[l][r][1] << ' ' << f[l][r][2] << '\n'; } } } inline void solve(int le) { if (le >= ans) return; int sz = 0; for (int l = 1, r = 1; l <= k; l++) { while (r <= k && p[r].I <= p[l].I + le) { int val = p[r++].I; if (val > num[sz]) num[++sz] = val; } if (p[l].I + le + 1 > num[sz]) num[++sz] = p[l].I + le + 1; } for (int i = 1, l = 1, r = 1; i <= sz; i++) { while (l <= k && !(p[l].I <= num[i] && num[i] <= p[l].I + le)) l++; r = max(r, l); while (r <= k && p[r].I <= num[i] && num[i] <= p[r].I + le) r++; if (l > k) cur[i] = {INF, INF, INF}; else cur[i] = f[l][r - 1]; } for (int l = 1, r = 1; l <= sz; l++) { r = max(r, l); while (r <= sz && num[r] < num[l] + n) { L.add({cur[r][0], r}); R.add({cur[r][1], r}); M.add({cur[r][2], r++}); } // cout << le << ' ' << L.get() << ' ' << R.get() << ' ' << M.get() << '\n'; ans = min(ans, 1ll * le + 1ll * max(L.get() + R.get(), M.get())); L.del(l); R.del(l); M.del(l); } } int main() { for (int i = 1; i <= k; i++) cin >> p[i].I >> p[i].II; vector<int> t; sort(p + 1, p + k + 1); for (int i = 1; i <= k; i++) { t.pb(p[i].I - 1); t.pb(n - p[i].I); for (int j = 1; j <= k; j++) { t.pb(max(0, p[j].I - p[i].I - 1)); t.pb(p[i].I - 1 + n - p[j].I); } } sort(t.begin(), t.end()); t.resize(unique(t.begin(), t.end()) - t.begin()); // for (auto c : t) cout << c << ' ';cout << '\n'; int xx = t.size() - 1; for (int i = 1; i <= 100000; i++) { int u = Rand(0, xx), v = Rand(0, xx); swap(t[u], t[v]); } init(); for (auto l : t) solve(l); cout << ans; return 0; } } int32_t main() { #define TASKNAME "" ios_base::sync_with_stdio(0); cin.tie(0); if (fopen(TASKNAME".inp","r" )) { freopen(TASKNAME".inp","r",stdin); freopen(TASKNAME".ans","w",stdout); } cin >> n >> m >> k; // if (max(n, m) <= 40) sub1 :: main(); else // if (k <= 25) sub2 :: main(); else sub3 :: main(); return 0; }

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

cultivation.cpp: In function 'long long int Rand(long long int, long long int)':
cultivation.cpp:21:17: error: call of overloaded 'abs(long long unsigned int)' is ambiguous
   21 |     return l+abs(rd()*1ll*rd())%(r-l+1);
      |              ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/std_abs.h:38,
                 from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from cultivation.cpp:4:
/usr/include/stdlib.h:848:12: note: candidate: 'int abs(int)'
  848 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/11/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from cultivation.cpp:4:
/usr/include/c++/11/bits/std_abs.h:103:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  103 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/11/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
cultivation.cpp: In function 'int32_t main()':
cultivation.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(TASKNAME".ans","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~