oj.uz

Submission #380440

# Submission time Handle Problem Language Result Execution time Memory
380440 2021-03-21T19:21:56 Z yrn_alf Hokej (COCI17_hokej) C++17
108 / 120
 1000 ms 44804 KB 
#pragma GCC optimize("Ofast,unroll-loops,shrink-wrap-separate,loop-nest-optimize")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native,avx,avx2,fma")

#include <bits/stdc++.h>
#include <tr1/unordered_map>
#include <tr1/unordered_set>
// #include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define mat vector<vector<ll>>
#define mat2 vector<vector<mat>>
#define vi vector<int>
#define vll vector<ll>
#define lll __int128_t
#define psi pair<string, int>
#define pis pair<int, string>
#define pic pair<int, char>
#define pcc pair<char, char>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define piiii pair<pii, pii>
#define mii map<int, int>
#define umii tr1::unordered_map<int, int>
#define iter multiset<pair<pll, ll>>::iterator
#define lb lower_bound
#define ub upper_bound

/*
#define fi first
#define se second
*/

/*
#define fi first.first
#define se first.second
#define th second.first
#define fo second.second
*/

/*
#define piii pair<int, pii>
#define fi first
#define se second.fi
#define th second.second
*/


#define piii pair<pii, int>
#define fi first.first
#define se first.th
#define th second


#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;
// using namespace __gnu_cxx;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ost;

const int nax = 500005, block = 320, dax = 2, lim = 2187, lgax = 25, bit = 64, mod = 1000000007, inf = 1000000007;
const ll llax = 1e18;
const double pi = acos(0) * 2, eps = 1e-6;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/*
const int MAX_MEM = 100000000;
int mpos;
char mem[MAX_MEM];
inline void* operator new(size_t n) {
    assert((mpos += n) <= MAX_MEM);
    return (void*)(mem + mpos - n);
}
inline void operator delete(void*) {}
*/


inline int read() {
    char c = getchar_unlocked();
    int t = 0, f = 1;
    while (!isdigit(c) && c != EOF)
        f = (c == '-' ? -1 : 1), c = getchar_unlocked();
    while (isdigit(c) && c != EOF)
        t = t * 10 + c - '0', c = getchar_unlocked();
    return t * f;
}

inline void read(char* s) {
    char c = getchar_unlocked();
    while (isspace(c))
        c = getchar_unlocked();
    while (!isspace(c))
        *s++ = c, c = getchar_unlocked();
    *s = '\0';
}


/*
struct chash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
*/

vector<int> a[nax];
ll ans;
vector<pair<pll, ll>> ord, ans1;
multiset<pll> s;

int main() {
    //IOS
    //freopen("in", "r", stdin);
    //freopen("out1", "w", stdout);
    int m = read(), n = read();
    for (int i = 1; i <= n; ++i) {
        int c = read(), l = read();
        ord.pb({{c, l}, i});
    }
    sort(rall(ord));
    int idx, cur;
    for (idx = 0, cur = 0; cur < m * 6; cur += ord[idx++].se) {}
    ord[--idx].se -= cur - m * 6;
    for (int i = 0; i <= idx; ++i)
        s.insert({ord[i].se, i}), ans += ord[i].fi * ord[i].se;
    int j = 0;
    while (s.rbegin()->first) {
        a[j].resize(6);
        for (int i = 0; i < 6; ++i)
            a[j][i] = (--s.end())->second, s.erase(--s.end());
        for (int i = 0; i < 6; ++i)
            s.insert({--ord[a[j][i]].se, a[j][i]});
        for (int i = 0; i < 6; ++i)
            a[j][i] = ord[a[j][i]].th;
        sort(all(a[j]));
        ++j;
    }
    sort(a, a + j);
    printf("%lld\n", ans);
    for (int i = 0; i < 6; ++i)
        printf("%d ", a[0][i]);
    for (int i = 0; i + 1 < j; ++i) {
        vi tmp, tmp1;
        for (int k = 0; k < 6; ++k)
            if (find(all(a[i + 1]), a[i][k]) == a[i + 1].end())
                tmp.pb(a[i][k]);
        for (int k = 0; k < 6; ++k)
            if (find(all(a[i]), a[i + 1][k]) == a[i].end())
                ans1.pb({{i + 1, tmp.back()}, a[i + 1][k]}), tmp.pop_back();
    }
    printf("\n%d\n", (int)ans1.size());
    for (pair<pll, ll> p : ans1)
        printf("%lld %lld %lld\n", p.fi, p.se, p.th);
    return 0;
}

Subtask #1
108.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 15 ms 12396 KB Output is correct
3 Correct 693 ms 28672 KB Output is correct
4 Correct 13 ms 12268 KB Output is correct
5 Correct 295 ms 19432 KB Output is correct
6 Correct 10 ms 12396 KB Output is correct
7 Correct 12 ms 12716 KB Output is correct
8 Correct 99 ms 19164 KB Output is correct
9 Correct 841 ms 42816 KB Output is correct
10 Execution timed out 1004 ms 44804 KB Time limit exceeded