| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 334615 |
2020-12-09T15:05:40 Z |
tengiz05 |
Gift (IZhO18_nicegift) |
C++17 |
|
54 ms |
13164 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 2e5+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, m, k;
vector<pii> v[N];
int s[N];
void solve(int test_case){
int i, j;
cin >> n >> k;
int sum = 0;
int mx = 0;
for(i=0;i<n;i++){
cin >> a[i];
sum += a[i];mx = max(mx, a[i]);
}
if(sum%k != 0 || sum < mx*k){
cout << -1 << '\n';
return;
}
int c = 0;
int need = sum/k;
for(i=0;i<n;i++){
if(need==s[c]){
c++;
}
if(need-s[c] >= a[i]){
s[c] += a[i];
// cout << c << ';' << i << ' ' << a[i] << '\n';
v[c].pb({a[i], i+1});
}else {
v[c].pb({need-s[c], i+1});
a[i] -= need-s[c];
s[c] = need;i--;
}
}
/* for(i=0;i<k;i++){
cout << "i = " << i << '\n';
for(auto [x,y] : v[i]){
cout << x << ' ' << y << '\n';
}cout << "\n\n";
}*/
vector<vector<int>> ans;
int itr = 0;
while(true){
itr++;
// if(itr>100)break;
bool ok = true;
for(i=0;i<k;i++)if(v[i].size())ok = false;
if(ok)break;
int mn = 2e18;
for(i=0;i<k;i++){
if(!v[i].size())continue;
mn = min(v[i].back().ff, mn);
}
vector<int> tmp;
tmp.pb(mn);
for(i=0;i<k;i++){
if(!v[i].size())continue;
int lst = v[i].size()-1;
v[i][lst].ff -= mn;
tmp.pb(v[i][lst].ss);
if(v[i][lst].ff == 0)v[i].pop_back();
}
ans.pb(tmp);
}
cout << ans.size() << '\n';
for(auto X : ans){
for(auto x : X)cout << x << ' ';
cout << '\n';
}
return;
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int ___T;
cin >> ___T;
for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
nicegift.cpp: In function 'void solve(long long int)':
nicegift.cpp:18:9: warning: unused variable 'j' [-Wunused-variable]
18 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
n=4 |
| 2 |
Correct |
3 ms |
4972 KB |
n=3 |
| 3 |
Correct |
3 ms |
4972 KB |
n=3 |
| 4 |
Correct |
4 ms |
4972 KB |
n=4 |
| 5 |
Correct |
3 ms |
4972 KB |
n=4 |
| 6 |
Correct |
3 ms |
4972 KB |
n=2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
n=4 |
| 2 |
Correct |
3 ms |
4972 KB |
n=3 |
| 3 |
Correct |
3 ms |
4972 KB |
n=3 |
| 4 |
Correct |
4 ms |
4972 KB |
n=4 |
| 5 |
Correct |
3 ms |
4972 KB |
n=4 |
| 6 |
Correct |
3 ms |
4972 KB |
n=2 |
| 7 |
Correct |
3 ms |
4972 KB |
n=5 |
| 8 |
Correct |
3 ms |
4972 KB |
n=8 |
| 9 |
Correct |
3 ms |
4972 KB |
n=14 |
| 10 |
Correct |
3 ms |
4972 KB |
n=11 |
| 11 |
Correct |
31 ms |
9188 KB |
n=50000 |
| 12 |
Correct |
32 ms |
9320 KB |
n=50000 |
| 13 |
Correct |
4 ms |
5100 KB |
n=10 |
| 14 |
Correct |
4 ms |
5100 KB |
n=685 |
| 15 |
Correct |
4 ms |
5100 KB |
n=623 |
| 16 |
Correct |
4 ms |
5100 KB |
n=973 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
n=4 |
| 2 |
Correct |
3 ms |
4972 KB |
n=3 |
| 3 |
Correct |
3 ms |
4972 KB |
n=3 |
| 4 |
Correct |
4 ms |
4972 KB |
n=4 |
| 5 |
Correct |
3 ms |
4972 KB |
n=4 |
| 6 |
Correct |
3 ms |
4972 KB |
n=2 |
| 7 |
Correct |
3 ms |
4972 KB |
n=5 |
| 8 |
Correct |
3 ms |
4972 KB |
n=8 |
| 9 |
Correct |
3 ms |
4972 KB |
n=14 |
| 10 |
Correct |
3 ms |
4972 KB |
n=11 |
| 11 |
Correct |
31 ms |
9188 KB |
n=50000 |
| 12 |
Correct |
32 ms |
9320 KB |
n=50000 |
| 13 |
Correct |
4 ms |
5100 KB |
n=10 |
| 14 |
Correct |
4 ms |
5100 KB |
n=685 |
| 15 |
Correct |
4 ms |
5100 KB |
n=623 |
| 16 |
Correct |
4 ms |
5100 KB |
n=973 |
| 17 |
Correct |
5 ms |
5228 KB |
n=989 |
| 18 |
Correct |
4 ms |
5100 KB |
n=563 |
| 19 |
Correct |
5 ms |
5228 KB |
n=592 |
| 20 |
Correct |
6 ms |
5228 KB |
n=938 |
| 21 |
Correct |
5 ms |
5228 KB |
n=747 |
| 22 |
Correct |
5 ms |
5228 KB |
n=991 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
13164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4972 KB |
n=4 |
| 2 |
Correct |
3 ms |
4972 KB |
n=3 |
| 3 |
Correct |
3 ms |
4972 KB |
n=3 |
| 4 |
Correct |
4 ms |
4972 KB |
n=4 |
| 5 |
Correct |
3 ms |
4972 KB |
n=4 |
| 6 |
Correct |
3 ms |
4972 KB |
n=2 |
| 7 |
Correct |
3 ms |
4972 KB |
n=5 |
| 8 |
Correct |
3 ms |
4972 KB |
n=8 |
| 9 |
Correct |
3 ms |
4972 KB |
n=14 |
| 10 |
Correct |
3 ms |
4972 KB |
n=11 |
| 11 |
Correct |
31 ms |
9188 KB |
n=50000 |
| 12 |
Correct |
32 ms |
9320 KB |
n=50000 |
| 13 |
Correct |
4 ms |
5100 KB |
n=10 |
| 14 |
Correct |
4 ms |
5100 KB |
n=685 |
| 15 |
Correct |
4 ms |
5100 KB |
n=623 |
| 16 |
Correct |
4 ms |
5100 KB |
n=973 |
| 17 |
Correct |
5 ms |
5228 KB |
n=989 |
| 18 |
Correct |
4 ms |
5100 KB |
n=563 |
| 19 |
Correct |
5 ms |
5228 KB |
n=592 |
| 20 |
Correct |
6 ms |
5228 KB |
n=938 |
| 21 |
Correct |
5 ms |
5228 KB |
n=747 |
| 22 |
Correct |
5 ms |
5228 KB |
n=991 |
| 23 |
Runtime error |
54 ms |
13164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 24 |
Halted |
0 ms |
0 KB |
- |
