제출 #346941

#제출 시각아이디문제언어결과실행 시간메모리
346941impetus_Gift (IZhO18_nicegift)C++14
100 / 100
1399 ms97172 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define f first #define s second #define ll long long #define int ll #define forn(i, a, b) for(int i = (a); i <= (b); ++i) #define forev(i, b, a) for(int i = (b); i >= (a); --i) #define VAR(v, i) __typeof( i) v=(i) #define forit(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout); using namespace std; const int maxn = (int)1e6 + 10; const int mod = (int)1e9 + 7; const int P = (int) 1e6 + 7; const double pi = acos(-1.0); #define inf mod typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> Vll; typedef vector<pair<int, int> > vpii; typedef vector<pair<ll, ll> > vpll; typedef array<int, 3> triple; int n, k, sum, mx; pii a[maxn]; priority_queue<pii> s; inline void solve(){ scanf("%lld%lld", &n, &k); forn(i, 1, n) { scanf("%lld", &a[i].f); a[i].s = i; sum += a[i].f; mx = max(mx, a[i].f); s.push(a[i]); } if(sum % k || sum / k < mx){ puts("-1"); return; } vector<pair<int, vi> > path; while(1){ int f = s.top().f, r; vi cur; vpii toAdd; forn(i, 1, k) { pii val = s.top(); toAdd.pb(val); cur.pb(val.s); r = val.f; s.pop(); } int nmx; if(sz(s)){ nmx = s.top().f; }else nmx = 0; if(!f) break; int res = min(r, (sum - nmx * k) / k); /*(sum - mid * k) / k >= nmx sum - mid * k >= nmx * k sum - nmx * k >= mid * k 7 >= 2 3 while(l <= r){ int mid = (l + r) >> 1; int curS = sum - mid * k, mx = nmx; if(curS / k >= mx){ res = mid; l = mid + 1; }else r = mid - 1; } assert(res != -1); */ for(auto x : toAdd) s.push({x.f - res, x.s}); sum -= res * k; path.pb({res, cur}); } printf("%lld\n", sz(path)); for(auto x : path){ printf("%lld ", x.f); for(auto it : x.s) printf("%lld ", it); puts(""); } } main () { srand(time(0)); int t = 1; //scanf("%d", &t); while(t--) solve(); }

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

nicegift.cpp:111:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main () {
      |       ^
nicegift.cpp: In function 'void solve()':
nicegift.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%lld%lld", &n, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
nicegift.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     scanf("%lld", &a[i].f);
      |     ~~~~~^~~~~~~~~~~~~~~~~
nicegift.cpp:57:24: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     int f = s.top().f, r;
      |                        ^
#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...