oj.uz

Submission #405186

# Submission time Handle Problem Language Result Execution time Memory
405186 2021-05-15T20:30:52 Z ly20 Carnival Tickets (IOI20_tickets) C++17
14 / 100
 955 ms 81340 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1512;
int tb[MAXN][MAXN];
vector <int> v0[MAXN], v1[MAXN];
int id0[MAXN], id1[MAXN];
int n, m;
int resp[MAXN][MAXN];
long long find_maximum(int k, vector<vector<int>> x) {
	n = x.size();
	m = x[0].size();
	long long mx = 0;
	vector <vector <int> > answer;
 	//answer.push_back(temp);
 	set <pair <int, int> > s0, s1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(x[i][j] == 0) v0[i].push_back(j);
            else v1[i].push_back(j);
            resp[i][j] = -1;
        }
    }
    for(int i = 0; i < n; i++) {
        s0.insert(make_pair(v0[i].size(), i));
        s1.insert(make_pair(v1[i].size(), -i));
    }
    long long rs = 0;
 	for(int i = 0; i < k; i++) {
        int qt0, qt1;
        int ot = n / 2;
        int qta, qtb;
        if(s0.size() >= ot && s1.size() >= ot) {
            qta = ot; qtb = ot;
        }
        else if(s0.size() < ot) {
            qta = s0.size();
            qtb = n - qta;
        }
        else {
            qtb = s1.size();
            qta = n - qtb;
        }
        rs += min(qta, qtb);
        vector <pair <int, int> > ida;
        for(int j = 0; j < qta; j++) {
            pair <int, int> a = (*(--s0.end()));
            int ia = a.second;
            s0.erase(--s0.end());
            a.first--;
            resp[ia][v0[ia][id0[ia]]] = i;
            id0[ia]++;
            if(a.first != 0) ida.push_back(a);
        }
        for(int j = 0; j < ida.size(); j++) s0.insert(ida[j]);
        vector <pair <int, int> > idb;
        for(int j = 0; j < qtb; j++) {
            pair <int, int> b = (*(--s1.end()));
            int ib = -b.second;
            s1.erase(--s1.end());
            b.first--;
            resp[ib][v1[ib][id1[ib]]] = i;
            id1[ib]++;
            if(b.first != 0) idb.push_back(b);
        }
        for(int j = 0; j < idb.size(); j++) s1.insert(idb[j]);
 	}
 	for(int i = 0; i < n; i++) {
        vector <int> row;
        for(int j = 0; j < m; j++) {
            row.push_back(resp[i][j]);
        }
        answer.push_back(row);
 	}
	allocate_tickets(answer);
	return rs;
}

Compilation message

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:34:22: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if(s0.size() >= ot && s1.size() >= ot) {
      |            ~~~~~~~~~~^~~~~
tickets.cpp:34:41: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |         if(s0.size() >= ot && s1.size() >= ot) {
      |                               ~~~~~~~~~~^~~~~
tickets.cpp:37:27: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         else if(s0.size() < ot) {
      |                 ~~~~~~~~~~^~~~
tickets.cpp:56:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int j = 0; j < ida.size(); j++) s0.insert(ida[j]);
      |                        ~~^~~~~~~~~~~~
tickets.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j = 0; j < idb.size(); j++) s1.insert(idb[j]);
      |                        ~~^~~~~~~~~~~~
tickets.cpp:31:13: warning: unused variable 'qt0' [-Wunused-variable]
   31 |         int qt0, qt1;
      |             ^~~
tickets.cpp:31:18: warning: unused variable 'qt1' [-Wunused-variable]
   31 |         int qt0, qt1;
      |                  ^~~
tickets.cpp:14:12: warning: unused variable 'mx' [-Wunused-variable]
   14 |  long long mx = 0;
      |            ^~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 33 ms 4800 KB Output is correct
6 Correct 775 ms 77908 KB Output is correct
7 Correct 836 ms 78288 KB Output is correct
8 Correct 5 ms 1100 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 9 ms 1668 KB Output is correct
13 Correct 29 ms 4876 KB Output is correct
14 Correct 30 ms 3524 KB Output is correct
15 Correct 955 ms 81340 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 564 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -