Submission #378855

#TimeUsernameProblemLanguageResultExecution timeMemory
378855casperwangGift (IZhO18_nicegift)C++14
100 / 100
928 ms90392 KiB
#include <bits/stdc++.h> #define int long long #define pb emplace_back #define pii pair<int,int> #define ff first #define ss second #define All(x) x.begin(), x.end() using namespace std; #define debug(args...) kout("[ " + string(#args) + " ]", args) void kout() { cerr << endl; } template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); } template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; } const int MAXN = 1000000; int N, K; int v[MAXN+1]; int sum, mmax; vector <pii> arr; set <int> num; vector <int> ans; void update(int x) { if (x > 0) num.erase(x); else num.insert(-x); } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); cin >> N >> K; for (int i = 1; i <= N; i++) { cin >> v[i]; sum += v[i]; mmax = max(mmax, v[i]); } if (sum % K || mmax > sum / K) { cout << -1 << '\n'; } else { int now = 0; for (int i = 1; i <= N; i++) { arr.pb(now, -i); now += v[i]; if (now > sum / K) { arr.pb(sum / K, i); now -= sum / K; arr.pb(0, -i); } arr.pb(now, i); } sort(All(arr)); int pre; for (int i = 0; i < arr.size(); i++) { if (i) { ans.pb(arr[i].ff - pre); for (int j : num) ans.pb(j); } pre = arr[i].ff; update(arr[i].ss); while (i+1 < arr.size() && arr[i+1].ff == arr[i].ff) { update(arr[++i].ss); } } cout << ans.size() / (K+1) << '\n'; for (int i = 0; i < ans.size(); i++) cout << ans[i] << " \n"[i%(K+1)==K]; } }

Compilation message (stderr)

nicegift.cpp: In function 'int main()':
nicegift.cpp:53:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int i = 0; i < arr.size(); i++) {
      |                   ~~^~~~~~~~~~~~
nicegift.cpp:60:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    while (i+1 < arr.size() && arr[i+1].ff == arr[i].ff) {
      |           ~~~~^~~~~~~~~~~~
nicegift.cpp:65:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int i = 0; i < ans.size(); 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...