oj.uz

답안 #927449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927449 2024-02-14T21:29:53 Z galen_colin Uplifting Excursion (BOI22_vault) C++17
0 / 100
 11 ms 4444 KB 
#include "bits/stdc++.h"
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

/* 
find my code templates at https://github.com/galencolin/cp-templates
also maybe subscribe please thanks 
*/

#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(NULL);}
#define f first
#define s second
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}

using ll = long long;
// using ll = int;
// #pragma warning("int")
//
using vl = vector<ll>;
using pl = pair<ll, ll>;

typedef long double ld;
typedef unsigned long long ull;

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds; 

template <typename num_t>
using ordered_set = tree<num_t, null_type, less<num_t>, rb_tree_tag, tree_order_statistics_node_update>;

// benq - print any container + pair
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
    cout << "["; 
    for (auto it = v.begin(); it != v.end();) {
        cout << *it;
        if (++it != v.end()) cout << ", ";
    }
    return cout << "]";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
    cin >> p.first;
    return cin >> p.second;
}

template<typename T> void debug(string s, T x) {cerr << "\033[1;34m" << s << "\033[0;32m = \033[35m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
        if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;34m" << s.substr(0, i) << "\033[0;32m = \033[35m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
template<typename T> void debug_nameless(T x) {cerr << "\033[35m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug_nameless(T x, Args... args) {cerr << "\033[35m" << x << "\033[31m | "; debug_nameless(args...);}

#ifdef galen_colin_local
#define pr(...) debug(#__VA_ARGS__, __VA_ARGS__)
#define prs(...) debug_nameless(__VA_ARGS__)
const bool local_ = true;
#else
#define pr(...) 135
#define prs(...) 135
const bool local_ = false;
#endif

mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 rng(61378913);
/* usage - just do rng() */

void usaco(string filename) {
// #pragma message("be careful, freopen may be wrong")
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

// #include <atcoder/all>
// using namespace atcoder;

const ld pi = 3.14159265358979323846;
// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;



ll n, m, q, k, l, r, x, y, z;
const ll template_array_size = 1e6 + 206171;
ll a[template_array_size];
ll b[template_array_size];
ll c[template_array_size];
string s, t;

ll ct[605];
ll& gc(ll v) {
    return ct[v + n];
}
ll take[605];
ll& gt(ll v) {
    return take[v + n];
}
ll dp[200005];
ll ndp[200005];

const bool run = local_ ? 0 : 1;
void solve(int tc = 0) {
    cin >> n >> k;

    for (ll i = -n; i <= n; i++) cin >> gc(i);

    ll t = 0, s = 0;
    for (ll i = -n; i <= n; i++) {
        t += gc(i);
        s += i * gc(i);
    }
    s -= k;

    ll r = 0;
    for (ll i = -n; i < 0; i++) {
        if (s < 0) {
            ll v = abs(s) / abs(i);
            v = min(v, gc(i));
            s -= i * v;
            gc(i) -= v;
            gt(i) += v;
            r += v;
        }
    }
    for (ll i = n; i > 0; i--) {
        if (s > 0) {
            ll v = abs(s) / abs(i);
            v = min(v, gc(i));
            s -= i * v;
            gc(i) -= v;
            gt(i) += v;
            r += v;
        }
    }

    if (abs(s) > n) {
        cout << "impossible\n";
        return;
    }

    for (ll i = -n; i < 0; i++) swap(gt(i), gt(-i));

    pr(s);

    ll L = (abs(s) + 1) * n;

    memset(dp, 1, sizeof dp);
    dp[L] = 0;

    if (local_) {
        for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
    }

    for (ll i = n; i > 0; i--) {
        ll t = abs(i);
        {
            for (ll r = 0; r < t; r++) {
                deque<pl> dq;
                for (ll j = r; j <= 2 * L; j += t) {
                    ll kill = j - gc(i) * t;
                    if (dq.size() && dq.front().f < kill) dq.pop_front();

                    ll v = dp[j] - j / t;
                    while (dq.size() && dq.back().s >= v) dq.pop_back();
                    dq.push_back({j, v});
                    v = j / t;
                    ndp[j] = v + dq.front().s;
                }
            }
            memcpy(dp, ndp, sizeof dp);
        }

        if (local_) {
            pr(i, gc(i));
            for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
        }

        {
            for (ll r = 0; r < t; r++) {
                deque<pl> dq;
                for (ll j = r; j <= 2 * L; j += t) {
                    ll kill = j - gt(i) * t;
                    if (dq.size() && dq.front().f < kill) dq.pop_front();

                    ll v = dp[j] + j / t;
                    while (dq.size() && dq.back().s >= v) dq.pop_back();
                    dq.push_back({j, v});
                    v = -(j / t);
                    ndp[j] = v + dq.front().s;
                }
            }
            memcpy(dp, ndp, sizeof dp);
        }

        if (local_) {
            pr(i, gt(i));
            for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
        }
    }

    pr(5);

    for (ll i = -n; i < 0; i++) {
        ll t = abs(i);
        {
            for (ll r = 0; r < t; r++) {
                deque<pl> dq;
                for (ll j = 2 * L - r; j >= 0; j -= t) {
                    ll kill = j + gc(i) * t;
                    if (dq.size() && dq.front().f > kill) dq.pop_front();

                    ll v = dp[j] + j / t;
                    while (dq.size() && dq.back().s >= v) dq.pop_back();
                    dq.push_back({j, v});
                    v = -(j / t);
                    ndp[j] = v + dq.front().s;
                }
            }
            memcpy(dp, ndp, sizeof dp);
        }

        if (local_) {
            pr(i, gc(i));
            for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
        }

        {
            for (ll r = 0; r < t; r++) {
                deque<pl> dq;
                for (ll j = 2 * L - r; j >= 0; j -= t) {
                    ll kill = j + gt(i) * t;
                    if (dq.size() && dq.front().f > kill) dq.pop_front();

                    ll v = dp[j] - j / t;
                    while (dq.size() && dq.back().s >= v) dq.pop_back();
                    dq.push_back({j, v});
                    v = j / t;
                    ndp[j] = v + dq.front().s;
                }
            }
            memcpy(dp, ndp, sizeof dp);
        }

        if (local_) {
            pr(i, gt(i));
            for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
        }
    }

    pr(s, r);

    r += dp[s + L];
    pr(r);
    if (r > 1e16) {
        cout << "impossible\n";
        return;
    }
    r = t - r;

    cout << r << '\n';
}

int main() {
    #ifdef galen_colin_local
        auto begin = std::chrono::high_resolution_clock::now();
    #endif
    
    send help

    #ifndef galen_colin_local
        // usaco("evacuation");
    #endif
    
    // usaco("cowland");
    
    // freopen("tc.cpp", "r", stdin);
    // freopen("tc.cpp", "w", stdout);
    // freopen("tc2.cpp", "w", stdout);
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
        
    cout << setprecision(15) << fixed;
    cerr << setprecision(4) << fixed;

    
            
    int tc = 1;
    // if (local_)
    // if (!run)
    // cin >> tc;
    for (int t = 0; t < tc; t++) {
        pr(t); prs(string(50, '-'));
        solve(t);
        prs(string(50, '-') + "\n");
    }
    
    #ifdef galen_colin_local
        auto end = std::chrono::high_resolution_clock::now();
        cerr << setprecision(4) << fixed;
        cerr << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
    #endif
}

Compilation message

vault.cpp: In function 'void solve(int)':
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:151:5: note: in expansion of macro 'pr'
  151 |     pr(s);
      |     ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:159:38: note: in expansion of macro 'pr'
  159 |         for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
      |                                      ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:182:13: note: in expansion of macro 'pr'
  182 |             pr(i, gc(i));
      |             ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:183:42: note: in expansion of macro 'pr'
  183 |             for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
      |                                          ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:204:13: note: in expansion of macro 'pr'
  204 |             pr(i, gt(i));
      |             ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:205:42: note: in expansion of macro 'pr'
  205 |             for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
      |                                          ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:209:5: note: in expansion of macro 'pr'
  209 |     pr(5);
      |     ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:231:13: note: in expansion of macro 'pr'
  231 |             pr(i, gc(i));
      |             ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:232:42: note: in expansion of macro 'pr'
  232 |             for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
      |                                          ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:253:13: note: in expansion of macro 'pr'
  253 |             pr(i, gt(i));
      |             ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:254:42: note: in expansion of macro 'pr'
  254 |             for (ll j = -L; j <= L; j++) pr(j, dp[j + L]);
      |                                          ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:258:5: note: in expansion of macro 'pr'
  258 |     pr(s, r);
      |     ^~
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:261:5: note: in expansion of macro 'pr'
  261 |     pr(r);
      |     ^~
vault.cpp: In function 'int main()':
vault.cpp:66:17: warning: statement has no effect [-Wunused-value]
   66 | #define pr(...) 135
      |                 ^~~
vault.cpp:300:9: note: in expansion of macro 'pr'
  300 |         pr(t); prs(string(50, '-'));
      |         ^~
vault.cpp:67:18: warning: statement has no effect [-Wunused-value]
   67 | #define prs(...) 135
      |                  ^~~
vault.cpp:300:16: note: in expansion of macro 'prs'
  300 |         pr(t); prs(string(50, '-'));
      |                ^~~
vault.cpp:67:18: warning: statement has no effect [-Wunused-value]
   67 | #define prs(...) 135
      |                  ^~~
vault.cpp:302:9: note: in expansion of macro 'prs'
  302 |         prs(string(50, '-') + "\n");
      |         ^~~
vault.cpp: In function 'void usaco(std::string)':
vault.cpp:77:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
vault.cpp:78:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 10 ms 4444 KB Output is correct
7 Correct 11 ms 4444 KB Output is correct
8 Correct 10 ms 4444 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Incorrect 9 ms 4440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 10 ms 4444 KB Output is correct
7 Correct 11 ms 4444 KB Output is correct
8 Correct 10 ms 4444 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Incorrect 9 ms 4440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 7 ms 4444 KB Output is correct
6 Correct 6 ms 4444 KB Output is correct
7 Incorrect 6 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 7 ms 4444 KB Output is correct
6 Correct 6 ms 4444 KB Output is correct
7 Incorrect 6 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 7 ms 4444 KB Output is correct
6 Correct 6 ms 4444 KB Output is correct
7 Incorrect 6 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 10 ms 4444 KB Output is correct
7 Correct 11 ms 4444 KB Output is correct
8 Correct 10 ms 4444 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Incorrect 9 ms 4440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 7 ms 4444 KB Output is correct
6 Correct 6 ms 4444 KB Output is correct
7 Incorrect 6 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 10 ms 4444 KB Output is correct
7 Correct 11 ms 4444 KB Output is correct
8 Correct 10 ms 4444 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Incorrect 9 ms 4440 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 6 ms 4444 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 7 ms 4444 KB Output is correct
6 Correct 6 ms 4444 KB Output is correct
7 Incorrect 6 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 10 ms 4444 KB Output is correct
7 Correct 11 ms 4444 KB Output is correct
8 Correct 10 ms 4444 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Incorrect 9 ms 4440 KB Output isn't correct
11 Halted 0 ms 0 KB -