Submission #200911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
200911	2020-02-08T13:46:50 Z	SamAnd	Hokej (COCI17_hokej)	C++17	120 / 120	207 ms	8952 KB

hokej

#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
struct ban
{
    int i;
    int k, d;
};
bool operator<(const ban& a, const ban& b)
{
    return a.k < b.k;
}
bool so(const ban& a, const ban& b)
{
    return a.d < b.d;
}

int m, n;
ban a[N];

int u[6];
int p[6];
int s[6];

int q[N];

vector<pair<int, pair<int, int> > > v;

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; ++i)
    {
        a[i].i = i;
        scanf("%d%d", &a[i].k, &a[i].d);
    }
    sort(a + 1, a + n + 1);
    long long ans = 0;
    int j = 0;
    for (int i = n; i >= 1; --i)
    {
        a[i].d = min(a[i].d, m);
        while (1)
        {
            if (j == 6)
                break;
            if (u[j] + a[i].d <= m)
            {
                if (p[j] == 0)
                    s[j] = a[i].i;
                else
                {
                    if (u[j] != m)
                        v.push_back({u[j], {p[j], a[i].i}});
                }
                p[j] = a[i].i;
                ans += (a[i].d * 1LL * a[i].k);
                q[i] += (a[i].d);
                u[j] += a[i].d;
                a[i].d = 0;
                break;
            }
            else
            {
                if (p[j] == 0)
                    s[j] = a[i].i;
                else
                {
                    if (u[j] != m)
                        v.push_back({u[j], {p[j], a[i].i}});
                }
                p[j] = a[i].i;
                ans += ((m - u[j]) * 1LL * a[i].k);
                q[i] += (m - u[j]);
                a[i].d -= (m - u[j]);
                u[j] = m;
                ++j;
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        a[i].d = q[i];
    }
    sort(a + 1, a + n + 1, so);
    ans = 0;
    j = 0;
    memset(u, 0, sizeof u);
    memset(p, 0, sizeof p);
    memset(s, 0, sizeof s);
    v.clear();
    for (int i = n; i >= 1; --i)
    {
        a[i].d = min(a[i].d, m);
        while (1)
        {
            if (j == 6)
                break;
            if (u[j] + a[i].d <= m)
            {
                if (p[j] == 0)
                    s[j] = a[i].i;
                else
                {
                    if (u[j] != m)
                        v.push_back({u[j], {p[j], a[i].i}});
                }
                p[j] = a[i].i;
                ans += (a[i].d * 1LL * a[i].k);
                q[i] += (a[i].d);
                u[j] += a[i].d;
                a[i].d = 0;
                break;
            }
            else
            {
                if (p[j] == 0)
                    s[j] = a[i].i;
                else
                {
                    if (u[j] != m)
                        v.push_back({u[j], {p[j], a[i].i}});
                }
                p[j] = a[i].i;
                ans += ((m - u[j]) * 1LL * a[i].k);
                q[i] += (m - u[j]);
                a[i].d -= (m - u[j]);
                u[j] = m;
                ++j;
            }
        }
    }
    printf("%lld\n", ans);
    for (int i = 0; i < 6; ++i)
        printf("%d ", s[i]);
    printf("\n");
    sort(v.begin(), v.end());
    printf("%d\n", v.size());
    for (int i = 0; i < v.size(); ++i)
        printf("%d %d %d\n", v[i].first, v[i].second.first, v[i].second.second);
    return 0;
}

Compilation message

hokej.cpp: In function 'int main()':
hokej.cpp:138:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, std::pair<int, int> > >::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", v.size());
                    ~~~~~~~~^
hokej.cpp:139:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
hokej.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &n);
     ~~~~~^~~~~~~~~~~~~~~~
hokej.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i].k, &a[i].d);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	248 KB	Output is correct
2	Correct	7 ms	504 KB	Output is correct
3	Correct	14 ms	1016 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	9 ms	632 KB	Output is correct
6	Correct	6 ms	376 KB	Output is correct
7	Correct	8 ms	504 KB	Output is correct
8	Correct	41 ms	2680 KB	Output is correct
9	Correct	207 ms	8824 KB	Output is correct
10	Correct	202 ms	8952 KB	Output is correct