oj.uz

Submission #974447

# Submission time Handle Problem Language Result Execution time Memory
974447 2024-05-03T10:49:24 Z LucaIlie Carnival Tickets (IOI20_tickets) C++17
25 / 100
 784 ms 122428 KB 
#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

struct cell {
    int i, j, val;
};

const int MAX_N = 1500;
const int MAX_M = 1500;
const long long INF = 1e15;
int x[MAX_N + 1][MAX_M + 1];
long long sx[MAX_N + 1][MAX_M + 1];
vector<int> mins[MAX_N + 1], maxs[MAX_N + 1], minTake[MAX_N + 1], maxTake[MAX_N + 1];
bool isMax[MAX_N + 1];
vector<cell> cells;

long long find_maximum( int k, vector<vector<int>> X ) {
    int n = X.size();
    int m = X[0].size();
    vector<vector<int>> answer( n );
    long long sum = 0;

    for ( int i = 1; i <= n; i++ ) {
        answer[i - 1].resize( m );
        for ( int j = 1; j <= m; j++ ) {
            x[i][j] = X[i - 1][j - 1];
            sx[i][j] = sx[i][j - 1] + x[i][j];
            answer[i - 1][j - 1] = -1;
            cells.push_back( { i, j, x[i][j] } );
        }
    }

    sort( cells.begin(), cells.end(), []( cell x, cell y ) { return x.val < y.val; } );
    int minimums = 0;
    for ( int i = 0; i < n * m / 2 && minimums < n * k / 2; i++ ) {
        if ( mins[cells[i].i].size() == k )
            continue;
        minimums++;
        mins[cells[i].i].push_back( cells[i].j );
    }
    int maximums = 0;
    for ( int i = n * m - 1; i >= 0 && maximums < n * k / 2; i-- ) {
        if ( mins[cells[i].i].size() + maxs[cells[i].i].size() == k )
            continue;
        maximums++;
        maxs[cells[i].i].push_back( cells[i].j );
    }

    if ( minimums != n * k / 2 || maximums != n * k / 2 )
        exit( 2 );
    
    for ( int i = 1; i <= n; i++ )
        reverse( maxs[i].begin(), maxs[i].end() );

    for ( int pas = 0; pas < k; pas++ ) {
        for ( int i = 1; i <= n; i++ )
            isMax[i] = false;

        vector<pair<int, int>> maxx;
        for ( int i = 1; i <= n; i++ ) {
            if ( !maxs[i].empty() )
                maxx.push_back( { (mins[i].empty() ? 0 : x[i][maxs[i].back()]), i } );
        }
        sort( maxx.begin(), maxx.end() );
        for ( int i = 0; i < n / 2; i++ ) {
            isMax[maxx[i].second] = true;
            //printf( "%d\n", maxx[i].second );
            answer[maxx[i].second - 1][maxs[maxx[i].second].back() - 1] = pas;
            sum += x[maxx[i].second][maxs[maxx[i].second].back()];
            maxs[maxx[i].second].pop_back();
        }
        for ( int i = 1; i <= n; i++ ) {
            if ( isMax[i] )
                continue;
            if ( mins[i].empty() )
                exit( 1 );
            answer[i - 1][mins[i].back() - 1] = pas;
            sum -= x[i][mins[i].back()];
            mins[i].pop_back();
        }
    }

    allocate_tickets( answer );
    return sum;
}

Compilation message

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:38:38: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         if ( mins[cells[i].i].size() == k )
      |              ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
tickets.cpp:45:64: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |         if ( mins[cells[i].i].size() + maxs[cells[i].i].size() == k )
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 5 ms 15892 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 0 ms 2652 KB Contestant returned 2307346107 while correct return value is 2727881086.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2628 KB Output is correct
4 Incorrect 2 ms 3164 KB Contestant returned 1516 while correct return value is 1600.
5 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 4 ms 3332 KB Output is correct
5 Correct 29 ms 11240 KB Output is correct
6 Correct 5 ms 5176 KB Output is correct
7 Correct 10 ms 16452 KB Output is correct
8 Correct 784 ms 122428 KB Output is correct
9 Correct 742 ms 116904 KB Output is correct
10 Correct 702 ms 114620 KB Output is correct
11 Correct 765 ms 121156 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 3 ms 3164 KB Contestant returned 39141745836 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 3 ms 3164 KB Contestant returned 39141745836 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2908 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 5 ms 15892 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Incorrect 0 ms 2652 KB Contestant returned 2307346107 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -