oj.uz

Submission #341539

# Submission time Handle Problem Language Result Execution time Memory
341539 2020-12-30T00:15:48 Z ivan_tudor Gift (IZhO18_nicegift) C++14
30 / 100
 547 ms 75744 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
priority_queue <pair<long long, int>> pq;
long long v[N];
vector<vector<int>> ans;
vector<int> ansx;
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, k;
  cin>>n>>k;
  long long sum = 0, mx = 0;
  for(int i=1;i<=n;i++){
    cin>>v[i];
    pq.push({v[i], i});
    sum+=v[i];
    mx = max(mx, v[i]);
  }
  if(sum%k!=0 || sum/k < mx ){
    cout<<"-1\n";
    return 0;
  }
  long long op = sum / k;
  while(pq.size()){
    vector<int> aux;
    for(int i = 1 ;i <=k;i++){
      aux.push_back(pq.top().second);
      pq.pop();
    }
    long long mn = v[aux[aux.size() - 1]];
    long long nxt = 0;
    if(pq.size())
      nxt = pq.top().first;
    long long newX = min(mn, op - nxt);
    op -= newX;
    ansx.push_back(newX);
    ans.push_back(aux);
    for(auto x : aux){
      v[x] -= newX;
      if(v[x])
        pq.push({v[x], x});
    }
  }
  cout<<ans.size()<<"\n";
  for(int i= 0; i<ans.size();i++){
    cout<<ansx[i]<<" ";
    for(auto x : ans[i])
      cout<<x<<" ";
    cout<<"\n";
  }
  return 0;
}

Compilation message

nicegift.cpp: In function 'int main()':
nicegift.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int i= 0; i<ans.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 364 KB n=3
4 Correct 1 ms 384 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 364 KB n=3
4 Correct 1 ms 384 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 1 ms 364 KB n=8
9 Correct 1 ms 364 KB n=14
10 Correct 1 ms 364 KB n=11
11 Correct 26 ms 3816 KB n=50000
12 Correct 22 ms 3688 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 1 ms 364 KB n=685
15 Correct 1 ms 364 KB n=623
16 Correct 1 ms 364 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 364 KB n=3
4 Correct 1 ms 384 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 1 ms 364 KB n=8
9 Correct 1 ms 364 KB n=14
10 Correct 1 ms 364 KB n=11
11 Correct 26 ms 3816 KB n=50000
12 Correct 22 ms 3688 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 1 ms 364 KB n=685
15 Correct 1 ms 364 KB n=623
16 Correct 1 ms 364 KB n=973
17 Correct 1 ms 364 KB n=989
18 Correct 1 ms 364 KB n=563
19 Correct 1 ms 364 KB n=592
20 Correct 1 ms 364 KB n=938
21 Correct 1 ms 364 KB n=747
22 Correct 1 ms 364 KB n=991

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 547 ms 75744 KB Added number should be positive
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB n=4
2 Correct 1 ms 364 KB n=3
3 Correct 1 ms 364 KB n=3
4 Correct 1 ms 384 KB n=4
5 Correct 1 ms 364 KB n=4
6 Correct 1 ms 364 KB n=2
7 Correct 1 ms 364 KB n=5
8 Correct 1 ms 364 KB n=8
9 Correct 1 ms 364 KB n=14
10 Correct 1 ms 364 KB n=11
11 Correct 26 ms 3816 KB n=50000
12 Correct 22 ms 3688 KB n=50000
13 Correct 1 ms 364 KB n=10
14 Correct 1 ms 364 KB n=685
15 Correct 1 ms 364 KB n=623
16 Correct 1 ms 364 KB n=973
17 Correct 1 ms 364 KB n=989
18 Correct 1 ms 364 KB n=563
19 Correct 1 ms 364 KB n=592
20 Correct 1 ms 364 KB n=938
21 Correct 1 ms 364 KB n=747
22 Correct 1 ms 364 KB n=991
23 Incorrect 547 ms 75744 KB Added number should be positive
24 Halted 0 ms 0 KB -