oj.uz

Submission #479819

# Submission time Handle Problem Language Result Execution time Memory
479819 2021-10-13T09:30:03 Z stefantaga Carnival Tickets (IOI20_tickets) C++14
41 / 100
 813 ms 70720 KB 
#include "tickets.h"
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <bits/stdc++.h>

using namespace std;
int fr[1505];
long long sumtot[1505];
deque <pair <int,int> > ceaules[1505];
vector <vector <int> > matrfin;
bool compare(int a,int b)
{
    return ceaules[a].front().first+ceaules[a].back().first<ceaules[b].front().first+ceaules[b].back().first||(ceaules[a].front().first+ceaules[a].back().first==ceaules[b].front().first+ceaules[b].back().first&&sumtot[a]<sumtot[b]);
}
long long find_maximum(int k, std::vector<std::vector<int>> x)
{
    int i,j;
    int n = x.size();
    int m = x[0].size();
    for (i=0; i<n; i++)
    {
        for (j=0; j<m; j++)
        {
            sumtot[i]+=x[i][j];
            ceaules[i].push_back({x[i][j],j});
        }
    }
    matrfin.resize(n);
    for (i=0;i<n;i++)
    {
        matrfin[i].resize(m);
    }
    long long solfin=0;
    for (i=1; i<=k; i++)
    {
        vector <int> bonjour;
        for (j=0; j<n; j++)
        {
            fr[j]=0;
            bonjour.push_back(j);
        }
        sort (bonjour.begin(),bonjour.end(),compare);
        long long sum=0;
        for (j=0;j<n/2;j++)
        {
            sum=sum-ceaules[bonjour[j]].front().first;
            sumtot[bonjour[j]]-=ceaules[bonjour[j]].front().first;
            matrfin[bonjour[j]][ceaules[bonjour[j]].front().second]=i;
            ceaules[bonjour[j]].pop_front();
        }
        for (j=n/2;j<n;j++)
        {
            sum=sum+ceaules[bonjour[j]].back().first;
            sumtot[bonjour[j]]-=ceaules[bonjour[j]].back().first;
            matrfin[bonjour[j]][ceaules[bonjour[j]].back().second]=i;
            ceaules[bonjour[j]].pop_back();
        }
        solfin=solfin+sum;
    }
    for (i=0;i<n;i++)
    {
        for (j=0;j<m;j++)
        {
            matrfin[i][j]--;
        }
    }
    allocate_tickets(matrfin);
    return solfin;
}
#ifdef HOME
static int n;
static int m;
static int k;
static std::vector<std::vector<int>> d;
static std::vector<std::vector<int>> x;
static int called = 0;

static void check(bool cond, std::string message)
{
    if (!cond)
    {
        printf("%s\n", message.c_str());
        exit(0);
    }
}


void allocate_tickets( std::vector<std::vector<int>> _d)
{
    check(!called, "allocate_tickets called more than once");
    d = _d;
    check((int)d.size() == n, "allocate_tickets called with parameter of wrong size");
    for (int i = 0; i < n; i++)
    {
        check((int)d[i].size() == m, "allocate_tickets called with parameter of wrong size");
    }
    called = 1;
}

int main()
{
    assert(scanf("%d %d %d", &n, &m, &k) == 3);
    x.resize(n);
    for (int i = 0; i < n; i++)
    {
        x[i].resize(m);
        for (int j=0; j < m; j++)
        {
            assert(scanf("%d", &x[i][j]) == 1);
        }
    }
    fclose(stdin);

    long long answer = find_maximum(k, x);
    check(called, "failure to call allocate_tickets");
    printf("%lld\n", answer);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (j) printf(" ");
            printf("%d", d[i][j]);
        }
        printf("\n");
    }
    fclose(stdout);
    return 0;
}

#endif // HOME

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 26 ms 3916 KB Output is correct
6 Correct 659 ms 70700 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 3 ms 1484 KB Output is correct
5 Correct 36 ms 3992 KB Output is correct
6 Correct 757 ms 70720 KB Output is correct
7 Correct 716 ms 62292 KB Output is correct
8 Correct 4 ms 1484 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 1 ms 1228 KB Output is correct
11 Correct 1 ms 1228 KB Output is correct
12 Correct 8 ms 1952 KB Output is correct
13 Correct 23 ms 3548 KB Output is correct
14 Correct 26 ms 3560 KB Output is correct
15 Correct 813 ms 67936 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1228 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1228 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1228 KB Contestant returned 11 while correct return value is 13.
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 1 ms 1228 KB Output is correct
3 Correct 1 ms 1228 KB Output is correct
4 Correct 1 ms 1228 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Correct 1 ms 1228 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Correct 3 ms 1484 KB Output is correct
11 Correct 26 ms 3916 KB Output is correct
12 Correct 659 ms 70700 KB Output is correct
13 Correct 1 ms 1228 KB Output is correct
14 Correct 1 ms 1228 KB Output is correct
15 Correct 1 ms 1228 KB Output is correct
16 Correct 3 ms 1484 KB Output is correct
17 Correct 36 ms 3992 KB Output is correct
18 Correct 757 ms 70720 KB Output is correct
19 Correct 716 ms 62292 KB Output is correct
20 Correct 4 ms 1484 KB Output is correct
21 Correct 1 ms 1228 KB Output is correct
22 Correct 1 ms 1228 KB Output is correct
23 Correct 1 ms 1228 KB Output is correct
24 Correct 8 ms 1952 KB Output is correct
25 Correct 23 ms 3548 KB Output is correct
26 Correct 26 ms 3560 KB Output is correct
27 Correct 813 ms 67936 KB Output is correct
28 Incorrect 1 ms 1228 KB Contestant returned 11 while correct return value is 13.
29 Halted 0 ms 0 KB -