oj.uz

Submission #430616

# Submission time Handle Problem Language Result Execution time Memory
430616 2021-06-16T17:17:44 Z MeGustaElArroz23 Carnival Tickets (IOI20_tickets) C++14
25 / 100
 838 ms 82092 KB 
/////////////////

#include "tickets.h"
#include<bits/stdc++.h>

using namespace std;

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

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

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;
    }
	return 1;
}

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
0 / 16.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 #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 29 ms 3444 KB Output is correct
6 Correct 768 ms 74948 KB Output is correct
7 Correct 810 ms 77324 KB Output is correct
8 Correct 5 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 10 ms 1060 KB Output is correct
13 Correct 30 ms 2776 KB Output is correct
14 Correct 31 ms 2984 KB Output is correct
15 Correct 838 ms 82092 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 0 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 0 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 Incorrect 1 ms 204 KB WA in grader: failure to call allocate_tickets
8 Halted 0 ms 0 KB -