oj.uz

Submission #430677

# Submission time Handle Problem Language Result Execution time Memory
430677 2021-06-16T18:16:02 Z MeGustaElArroz23 Carnival Tickets (IOI20_tickets) C++14
41 / 100
 850 ms 77728 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;
}

vvi res;

int INF=2000000000;

int minind(int ind,vi v){
    int sol=v.size();
    v.push_back(INF);
    for (int i=0;i<v.size()-1;i++){
        if (res[ind][i]==-1 and v[i]<v[sol]) sol=i;
    }
    return sol;
}

int maxind(int ind,vi v){
    int sol=v.size();
    v.push_back(-1);
    for (int i=0;i<v.size()-1;i++){
        if (res[ind][i]==-1 and 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){
        res=vvi(n,vi(m,-1));
        vii indice(n);
        for (int i=0;i<n;i++) indice[i]=pii{minind(i,x[i]),maxind(i,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;
            }
        }
        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;
    }
    else{
        ll realsol=0;
        res=vvi(n,vi(m,-1));
        for (int dia=0;dia<k;dia++){
            vii indice(n);
            for (int i=0;i<n;i++) indice[i]=pii{minind(i,x[i]),maxind(i,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;
                }
            }
            for (int num:mejorizq) res[num][indice[num].fi]=dia;
            for (int num:mejorder) res[num][indice[num].se]=dia;
            realsol+=sol;
        }
        allocate_tickets(res);
        return realsol;
    }
    return 1;
}

Compilation message

tickets.cpp: In function 'int minind(int, 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()-1;i++){
      |                  ~^~~~~~~~~~~
tickets.cpp: In function 'int maxind(int, vi)':
tickets.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i=0;i<v.size()-1;i++){
      |                  ~^~~~~~~~~~~
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:139:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |             while (izq.size()<n/2-1 and v[j].se!=i){
      |                    ~~~~~~~~~~^~~~~~
tickets.cpp:150:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  150 |             if (izq.size()<n/2) continue;
      |                 ~~~~~~~~~~^~~~
tickets.cpp:182:34: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  182 |                 while (izq.size()<n/2-1 and v[j].se!=i){
      |                        ~~~~~~~~~~^~~~~~
tickets.cpp:193:31: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  193 |                 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 616 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 2 ms 332 KB Output is correct
5 Correct 26 ms 2384 KB Output is correct
6 Correct 677 ms 51304 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 31 ms 3264 KB Output is correct
6 Correct 788 ms 70684 KB Output is correct
7 Correct 846 ms 73036 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 30 ms 2776 KB Output is correct
14 Correct 24 ms 2780 KB Output is correct
15 Correct 850 ms 77728 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 204 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 204 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 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 616 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 2 ms 332 KB Output is correct
11 Correct 26 ms 2384 KB Output is correct
12 Correct 677 ms 51304 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 31 ms 3264 KB Output is correct
18 Correct 788 ms 70684 KB Output is correct
19 Correct 846 ms 73036 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 30 ms 2776 KB Output is correct
26 Correct 24 ms 2780 KB Output is correct
27 Correct 850 ms 77728 KB Output is correct
28 Incorrect 1 ms 204 KB Contestant returned 11 while correct return value is 13.
29 Halted 0 ms 0 KB -