Submission #234491

#	Time	Username	Problem	Language	Result	Execution time	Memory
234491		Vimmer	Hokej (COCI17_hokej)	C++14	0 / 120	1012 ms	65540 KiB

hokej

#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 500005
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9

using namespace std;

typedef long double ld;
typedef long long ll;

typedef short int si;


bool cmp(pair <pair <int, int>, int>  x, pair <pair <int, int>, int>  y)
{
    if (x.F.F != y.F.F) return x.F.F > y.F.F;

    return x.F.S > y.F.S;
}

set <int> gt[N];

int main()
{
   // freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> m >> n;

    int obr[n];

    vector <pair <pair <int, int>, int>  > g; g.resize(n);

    for (int i = 0; i < n; i++) {cin >> g[i].F.F >> g[i].F.S; g[i].S = i;}

    vector <pair <int, pair <int, int> > > vr; vr.clear();

    sort(g.begin(), g.end(), cmp);

    for (int i = 0; i < n; i++) obr[g[i].S] = i;

    int a[6];

    set <int> st; st.clear();

    set <pair <int, int> > se; se.clear();

    for (int i = 0; i < 6; i++) {a[i] = g[i].S; se.insert({g[i].F.S, g[i].S}); st.insert(g[i].S);}

    int j = 6, pos = 0;

    vector <pair <int, int> > gr; gr.clear();

    vector <pair <int, int> > ost; ost.clear();

    set <pair <int, int> > dob; dob.clear();

    for (int i = 1; i <= m; i++)
    {
        for (auto it : st) gt[it].insert(i);

        if (i == m) break;

        vector <int> gr; gr.clear();

        while (sz(se) > 0 && (*se.begin()).F == i)
        {
            gr.pb((*se.begin()).S);

            for (auto it : gt[gr.back()]) dob.insert({it, gr.back()});

            se.erase(se.begin());

            st.erase(gr.back());
        }

        while (sz(gr) > 0 && j < sz(g))
        {
            if (sz(dob) && pos < sz(ost))
            {
                int tm = (*dob.begin()).F, nm = (*dob.begin()).S;

                dob.erase(dob.begin());

                ost[pos].F--;

                st.insert(nm);

                se.insert({i + 1, nm});

                gr.pop_back();

                gt[ost[pos].S].insert(tm);

                gt[nm].erase(tm);

                if (ost[pos].F == 0) pos++;

                continue;
            }

            se.insert({i + g[j].F.S, g[j].S});

            st.insert(g[j].S);

            int ostr = max(0, (i + g[j].F.S) - m);

            if (ostr > 0) ost.pb({ostr, g[j].S});

            gr.pop_back();

            j++;
        }
    }

    ll ans = 0;

    vector <int> tmr[m + 1];

    for (int i = 0; i <= m; i++) tmr[i].clear();

    for (int i = 0; i < n; i++)
        for (auto it : gt[i]) {tmr[it].pb(i); ans += g[obr[i]].F.F;}

    cout << ans << endl;

    for (int i = 0; i < 6; i++) a[i] = tmr[1][i];

    sort(a, a + 6);

    vector <int> pr; pr.clear();

    for (int i = 0; i < 6; i++) {pr.pb(a[i]); cout << a[i] + 1 << " "; } cout << endl;

    for (int i = 2; i <= m; i++)
    {
        sort(pr.begin(), pr.end());

        vector <int> grr = tmr[i];

        sort(grr.begin(), grr.end());

        vector <int> nw; nw.clear();

        int j = 0;

        while (j < sz(pr))
        {
            if (pr[j] == grr[j]) nw.pb(pr[j]);
            else
            {
                nw.pb(grr[j]);

                vr.pb({i, {pr[j], grr[j]}});
            }

            j++;
        }

       pr = nw;
    }

    cout << sz(vr) << endl;

    for (auto it : vr) cout << it.F << " " << it.S.F + 1 << " " << it.S.S + 1 << '\n';
}

• Subtask 1: 0 / 120