oj.uz

Submission #430652

# Submission time Handle Problem Language Result Execution time Memory
430652 2021-06-16T18:02:41 Z MeGustaElArroz23 Carnival Tickets (IOI20_tickets) C++14
41 / 100
 888 ms 77796 KB 
#include "tickets.h"
#include<bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef pair<pii,int> piii;
typedef vector<piii> viii;

bool casobinario(vvi v){
    for (vi w:v){
        for (int x:w){
            if (x>1) return 0;
        }
    }
    return 1;
}

int minind(vi v){
    int sol=0;
    for (int i=0;i<v.size();i++){
        if (v[i]<v[sol]) sol=i;
    }
    return sol;
}

int maxind(vi v){
    int sol=0;
    for (int i=0;i<v.size();i++){
        if (v[i]>v[sol]) sol=i;
    }
    return sol;
}

bool orden(piii a, piii b){ return a.fi.fi+a.fi.se<b.fi.fi+b.fi.se; }

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
    if (m==1){
        allocate_tickets(vvi(n,vi(1,0)));
        vi v;
        for (int i=0;i<n;i++) v.push_back(x[i][0]);
        sort(v.begin(),v.end());
        ll sol=0;
        for (int x:v) sol+=abs(v[n/2]-x);
        return sol;
    }
    else if (casobinario(x)){
        vvi unos(n);
        vvi ceros(n);
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                if (x[i][j]) unos[i].push_back(j);
                else ceros[i].push_back(j);
            }
        }
        set<pii> cantidad;
        for (int i=0;i<n;i++) cantidad.insert(pii{unos[i].size(),i});
        vvi res(n,vi(m,-1));
        vvi cadadia(k);
        for (int dia=0;dia<k;dia++){
            auto a=cantidad.begin();
            vii restar;
            for (int i=0;i<n/2;i++){
                int ac=(*a).second;
                if (ceros[ac].size()){
                    res[ac][ceros[ac][ceros[ac].size()-1]]=dia;
                    ceros[ac].pop_back();
                    cadadia[dia].push_back(0);
                }
                else{
                    res[ac][unos[ac][unos[ac].size()-1]]=dia;
                    unos[ac].pop_back();
                    restar.push_back((*a));
                    cadadia[dia].push_back(1);
                }
                a++;
            }
            for (int i=0;i<n/2;i++){
                int ac=(*a).second;
                if (unos[ac].size()){
                    res[ac][unos[ac][unos[ac].size()-1]]=dia;
                    unos[ac].pop_back();
                    restar.push_back((*a));
                    cadadia[dia].push_back(1);
                }
                else{
                    res[ac][ceros[ac][ceros[ac].size()-1]]=dia;
                    ceros[ac].pop_back();
                    cadadia[dia].push_back(0);
                }
                a++;
            }
            for (pii x:restar){
                cantidad.erase(x);
                cantidad.insert(pii{x.first-1,x.second});
            }
        }
        allocate_tickets(res);
        
        ll sol=0;
        for (vi v:cadadia){
            sort(v.begin(),v.end());
            for (int x:v) sol+=abs(v[n/2]-x);
        }
        return sol;
    }
	else if (k==1){
        vii indice(n);
        for (int i=0;i<n;i++) indice[i]=pii{minind(x[i]),maxind(x[i])};
        viii v(n);
        for (int i=0;i<n;i++) v[i]=piii{pii{x[i][indice[i].first],x[i][indice[i].second]},i};
        sort(v.begin(),v.end(),orden);
        ll sol=-1;
        vi mejorizq;
        vi mejorder;
        for (int i=0;i<n;i++){
            vi izq;
            vi der;
            int j=0;
            while (izq.size()<n/2-1 and v[j].se!=i){
                if (v[j].fi.fi<=x[i][indice[i].fi]) izq.push_back(v[j].se);
                else der.push_back(v[j].se);
                j++;
            }
            izq.push_back(v[j].se);
            j++;
            while (j<n){
                der.push_back(v[j].se);
                j++;
            }
            if (izq.size()<n/2) continue;
            ll suma=0;
            int median=x[i][indice[i].fi];
            for (int num:izq) suma+=median-x[num][indice[num].fi];
            for (int num:der) suma+=x[num][indice[num].se]-median;
            if (suma>sol){
                sol=suma;
                mejorizq=izq;
                mejorder=der;
            }
        }
        vvi res(n,vi(m,-1));
        for (int num:mejorizq) res[num][indice[num].fi]=0;
        for (int num:mejorder) res[num][indice[num].se]=0;
        allocate_tickets(res);
        return sol;
    }
    return 1;
}

Compilation message

tickets.cpp: In function 'int minind(vi)':
tickets.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i=0;i<v.size();i++){
      |                  ~^~~~~~~~~
tickets.cpp: In function 'int maxind(vi)':
tickets.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i=0;i<v.size();i++){
      |                  ~^~~~~~~~~
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:129:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  129 |             while (izq.size()<n/2-1 and v[j].se!=i){
      |                    ~~~~~~~~~~^~~~~~
tickets.cpp:140:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  140 |             if (izq.size()<n/2) continue;
      |                 ~~~~~~~~~~^~~~

Subtask #1
11.0 / 11.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 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 2 ms 588 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 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 28 ms 3124 KB Output is correct
6 Correct 681 ms 55420 KB Output is correct

Subtask #3
14.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 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 30 ms 3292 KB Output is correct
6 Correct 831 ms 70504 KB Output is correct
7 Correct 888 ms 72992 KB Output is correct
8 Correct 4 ms 588 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 8 ms 972 KB Output is correct
13 Correct 26 ms 2580 KB Output is correct
14 Correct 25 ms 2764 KB Output is correct
15 Correct 883 ms 77796 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: failure to call allocate_tickets
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: failure to call allocate_tickets
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB WA in grader: failure to call allocate_tickets
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.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 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 2 ms 588 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 28 ms 3124 KB Output is correct
12 Correct 681 ms 55420 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 3 ms 460 KB Output is correct
17 Correct 30 ms 3292 KB Output is correct
18 Correct 831 ms 70504 KB Output is correct
19 Correct 888 ms 72992 KB Output is correct
20 Correct 4 ms 588 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 8 ms 972 KB Output is correct
25 Correct 26 ms 2580 KB Output is correct
26 Correct 25 ms 2764 KB Output is correct
27 Correct 883 ms 77796 KB Output is correct
28 Incorrect 1 ms 204 KB WA in grader: failure to call allocate_tickets
29 Halted 0 ms 0 KB -