oj.uz

Submission #423772

# Submission time Handle Problem Language Result Execution time Memory
423772 2021-06-11T12:33:14 Z humbertoyusta Carnival Tickets (IOI20_tickets) C++14
27 / 100
 714 ms 77924 KB 
#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define all(x) x.begin() , x.end()
typedef long long ll;
typedef pair<int,int> ii;

long long find_maximum(int k, std::vector<std::vector<int>> x) {

	int n = x.size();
	int m = x[0].size();

	std::vector<std::vector<int>> answer, fans;
	for (int i = 0; i < n; i++) {
		std::vector<int> row(m);
		for (int j = 0; j < m; j++) {
            row[j] = -1;
		}
		answer.push_back(row);
		fans.pb(row);
	}

	ll res = 0;

	vector<vector<ii>> mat;
	for(int i=0; i<n; i++){
        vector<ii> row(m);
        for(int j=0; j<m; j++){
            row[j] = { x[i][j] , j };
        }
        sort(all(row));
        mat.pb(row);
	}

	for(int i=0; i<n; i++){
        for(int j=0; j<k; j++){
            res -= mat[i][j].f;
            fans[i][j] = 0;
        }
	}

	priority_queue<pair<int,ii>> q;

	for(int i=0; i<n; i++){
        q.push({mat[i][k-1].f + mat[i][m-1].f,{i,-1}});
	}

	for(int t=0; t<n*k/2; t++){

        pair<ll,ii> p = q.top();
        res += p.f;

        q.pop();

        fans[p.s.f][m+p.s.s] = 1;
        if( m != k ) fans[p.s.f][k+p.s.s] = -1;

        if( abs(p.s.s - 1) <= k ){
            p.s.s--;
            q.push({mat[p.s.f][k+p.s.s].f+mat[p.s.f][m+p.s.s].f,{p.s.f,p.s.s}});
        }
	}

	vector<int> mx(k), mn(k);
	for(int i=0; i<k; i++)
        mn[i] = mx[i] = n / 2;

    for(int i=0; i<n; i++){
        int c1 = 0, c2 = 0;
        for(int j=0; j<m; j++){
            if( fans[i][j] == 0 ){
                while( mn[c1] == 0 ) c1 = ( c1 + 1 ) % k;
                answer[i][j] = c1;
                mn[c1] --;
                c1 = ( c1 + 1 ) % k;
            }
            if( fans[i][j] == 1 ){
                while( mx[c1] == 0 ) c1 = ( c1 + 1 ) % k;
                answer[i][j] = c1;
                mx[c1] --;
                c1 = ( c1 + 1 ) % k;
            }
        }
    }

	allocate_tickets(answer);
	return res;
}

Compilation message

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:73:21: warning: unused variable 'c2' [-Wunused-variable]
   73 |         int c1 = 0, c2 = 0;
      |                     ^~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 844 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 33 ms 3424 KB Output is correct
6 Correct 714 ms 77924 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB There is multiple tickets of color 2 on day 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB There is multiple tickets of color 5 on day 2
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Incorrect 3 ms 588 KB There is multiple tickets of color 40 on day 0
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Incorrect 3 ms 588 KB There is multiple tickets of color 40 on day 0
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 33 ms 3424 KB Output is correct
12 Correct 714 ms 77924 KB Output is correct
13 Incorrect 0 ms 204 KB There is multiple tickets of color 2 on day 0
14 Halted 0 ms 0 KB -