Submission #136874

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136874	2019-07-26T12:22:01 Z	mariusnicoli	Hokej (COCI17_hokej)	C++14	36 / 120	526 ms	17096 KB

hokej

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;

struct player {
    long long value;
    long long resistence;
    long long position;
};

struct ch {
    long long minute;
    long long enter;
    long long exit;
};

player v[500010];
ch Change[1000001];
deque<int> Start;

long long change, start, n, m, rest, lin, col, i, j, sol, last;

long long cmp(const player &a, const player &b) {
    if (a.value != b.value)
        return a.value > b.value;
    else
        return a.resistence > b.resistence;
}

long long cmp1(const ch &a, const ch &b) {
    return a.minute < b.minute;
}

int main () {
    cin>>m>>n;
    for (i=1;i<=n;i++) {
        cin>>v[i].value>>v[i].resistence;
        v[i].position = i;
    }

    sort(v+1, v+n+1, cmp);
/**
    for (i=1;i<=n;i++) {
        cout<<v[i].value<<" "<<v[i].resistence<<" "<<v[i].position<<"\n";
    }
**/


    for (i=1;i<=6;i++) {
        if (v[i].resistence < m) {
            break;
        }
        Start.push_back(v[i].position);
        sol += v[i].value * m;
    }
    rest = 6*m - (i-1)*m;
    last = -1;

    col = 1;

    for (j=i;j<=n;j++) {

        if (v[j].resistence == m) {
            if (rest >= v[j].resistence) {
                sol += m*v[j].value;
                rest -= m;
                Start.push_front(v[j].resistence);
                if (rest == 0)
                    break;
            }
        }

        if (col == 1) {
            Start.push_back(v[j].position);
        }

        if (col != 1) {
            Change[++change].minute = col;
            Change[change].enter = v[j].position;
            Change[change].exit = last;
        }
        last = v[j].position;

        if (rest <= v[j].resistence) {
            sol += rest * v[j].value;
            break;
        }else {
            if (col + v[j].resistence <= m) {
                col += v[j].resistence;
            } else
                if (col + v[j].resistence == m+1) {
                    last =-1;
                    col = 1;
                } else {
                    Start[++start] = v[j].position;
                    col = v[j].resistence - (m-col);
                }
            rest -= v[j].resistence;
            sol += v[j].resistence * v[j].value;
        }
    }

    sort(Change+1, Change+change+1, cmp1);
    cout<<sol<<"\n";
    for (i=1;i<=6;i++) {
        cout<<Start.front()<<" ";
        Start.pop_front();
    }
    cout<<"\n";
    cout<<change<<"\n";
    for (i=1;i<=change;i++)
        cout<<Change[i].minute-1<<" "<<Change[i].exit<<" "<<Change[i].enter<<"\n";
    return 0;
}

Subtask #1

36.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Correct	11 ms	504 KB	Output is correct
3	Correct	30 ms	1276 KB	Output is correct
4	Incorrect	3 ms	376 KB	Output isn't correct
5	Correct	12 ms	632 KB	Output is correct
6	Incorrect	5 ms	504 KB	Output isn't correct
7	Incorrect	10 ms	632 KB	Output isn't correct
8	Incorrect	94 ms	3604 KB	Output isn't correct
9	Incorrect	526 ms	16968 KB	Output isn't correct
10	Incorrect	526 ms	17096 KB	Output isn't correct