oj.uz

Submission #645688

# Submission time Handle Problem Language Result Execution time Memory
645688 2022-09-27T16:18:58 Z mentaldora Gift (IZhO18_nicegift) C++14
30 / 100
 35 ms 7020 KB 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz size()
#define mk make_pair
#define ff first
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ull unsigned long long
#define ss second
#define all(x) x.begin(), x.end()
#define Resh cin>>tt;while(tt--)solve();
#define yes cout <<"Yes"<<"\n";
#define no cout <<"No"<<"\n";
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define left(v) v + v
#define right(v) v + v + 1
const long double PI = acos(-1);
const long long n6 = 1e6 + 10;
const long long n5 = 1e5+1;
const long long n4 = 1e4 + 10;
const long long inf = 1e9;
const long long mod = 16714589;
const int BL = 60090;
const long long MAXN = 1e5+5;

ll a[n5];
multiset<pll> ms;
vector<vector<pll>> ans;
main() {
    fast
    ll n, k, cnt=0;
    cin >> n >> k;
    for(int i = 1;i <= n;i++) {
        cin >> a[i];
        cnt+=a[i];
    }
    if(cnt % k) {
        cout << -1;
        return 0;
    }
    for(int i = 1;i <= n;i++) {
        ms.insert(mk(a[i], i));
    }
    pll p2 = *ms.rbegin();
    if(p2.ff > cnt/k) {
        cout << -1;
        return 0;
    }
    while(ms.sz >= k) {
        vector<pll> v;
        while(v.sz < k) {
            pll p = *ms.rbegin();
            p.ff--;
            v.pb(p);
            ms.erase(--ms.end());
        }
        for(auto c : v) {
            if(c.ff) {
                ms.insert(c);
            }
        }
        ans.pb(v);
    }
    cout << ans.size() <<'\n';
    for(auto c : ans) {
        cout << "1 ";
        for(auto t : c) {
            cout << t.ss << " ";
        }
        cout <<'\n';
    }
}

Compilation message

nicegift.cpp:1: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    1 | #pragma comment(linker, "/stack:200000000")
      | 
nicegift.cpp:34:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   34 | main() {
      | ^~~~
nicegift.cpp: In function 'int main()':
nicegift.cpp:54:17: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   54 |     while(ms.sz >= k) {
      |           ~~~~~~^~~~
nicegift.cpp:56:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   56 |         while(v.sz < k) {
      |               ~~~~~^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 340 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 1 ms 328 KB n=4
5 Correct 1 ms 328 KB n=4
6 Correct 1 ms 212 KB n=2

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 340 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 1 ms 328 KB n=4
5 Correct 1 ms 328 KB n=4
6 Correct 1 ms 212 KB n=2
7 Correct 1 ms 332 KB n=5
8 Correct 1 ms 336 KB n=8
9 Correct 7 ms 1424 KB n=14
10 Correct 6 ms 1108 KB n=11
11 Correct 34 ms 6824 KB n=50000
12 Correct 35 ms 7020 KB n=50000
13 Correct 21 ms 4232 KB n=10
14 Correct 23 ms 3752 KB n=685
15 Correct 27 ms 4112 KB n=623
16 Correct 14 ms 2444 KB n=973

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 340 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 1 ms 328 KB n=4
5 Correct 1 ms 328 KB n=4
6 Correct 1 ms 212 KB n=2
7 Correct 1 ms 332 KB n=5
8 Correct 1 ms 336 KB n=8
9 Correct 7 ms 1424 KB n=14
10 Correct 6 ms 1108 KB n=11
11 Correct 34 ms 6824 KB n=50000
12 Correct 35 ms 7020 KB n=50000
13 Correct 21 ms 4232 KB n=10
14 Correct 23 ms 3752 KB n=685
15 Correct 27 ms 4112 KB n=623
16 Correct 14 ms 2444 KB n=973
17 Correct 26 ms 3468 KB n=989
18 Correct 11 ms 1608 KB n=563
19 Correct 19 ms 2452 KB n=592
20 Correct 20 ms 2460 KB n=938
21 Correct 14 ms 1952 KB n=747
22 Correct 17 ms 2116 KB n=991

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 2016 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n=4
2 Correct 1 ms 340 KB n=3
3 Correct 0 ms 212 KB n=3
4 Correct 1 ms 328 KB n=4
5 Correct 1 ms 328 KB n=4
6 Correct 1 ms 212 KB n=2
7 Correct 1 ms 332 KB n=5
8 Correct 1 ms 336 KB n=8
9 Correct 7 ms 1424 KB n=14
10 Correct 6 ms 1108 KB n=11
11 Correct 34 ms 6824 KB n=50000
12 Correct 35 ms 7020 KB n=50000
13 Correct 21 ms 4232 KB n=10
14 Correct 23 ms 3752 KB n=685
15 Correct 27 ms 4112 KB n=623
16 Correct 14 ms 2444 KB n=973
17 Correct 26 ms 3468 KB n=989
18 Correct 11 ms 1608 KB n=563
19 Correct 19 ms 2452 KB n=592
20 Correct 20 ms 2460 KB n=938
21 Correct 14 ms 1952 KB n=747
22 Correct 17 ms 2116 KB n=991
23 Runtime error 15 ms 2016 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -