oj.uz

Submission #479817

# Submission time Handle Problem Language Result Execution time Memory
479817 2021-10-13T09:20:15 Z stefantaga Carnival Tickets (IOI20_tickets) C++14
27 / 100
 833 ms 72664 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[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[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 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 1 ms 1228 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 2 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 27 ms 4140 KB Output is correct
6 Correct 654 ms 70636 KB Output is correct

Subtask #3
0 / 14.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 3 ms 1448 KB Output is correct
5 Correct 29 ms 4100 KB Output is correct
6 Correct 754 ms 72664 KB Output is correct
7 Correct 833 ms 66656 KB Output is correct
8 Correct 4 ms 1576 KB Output is correct
9 Correct 1 ms 1228 KB Output is correct
10 Incorrect 1 ms 1228 KB Contestant returned 44 while correct return value is 45.
11 Halted 0 ms 0 KB -

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 1232 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 1232 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 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 1 ms 1228 KB Output is correct
5 Correct 1 ms 1356 KB Output is correct
6 Correct 2 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 27 ms 4140 KB Output is correct
12 Correct 654 ms 70636 KB Output is correct
13 Correct 2 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 1448 KB Output is correct
17 Correct 29 ms 4100 KB Output is correct
18 Correct 754 ms 72664 KB Output is correct
19 Correct 833 ms 66656 KB Output is correct
20 Correct 4 ms 1576 KB Output is correct
21 Correct 1 ms 1228 KB Output is correct
22 Incorrect 1 ms 1228 KB Contestant returned 44 while correct return value is 45.
23 Halted 0 ms 0 KB -