oj.uz

Submission #864786

# Submission time Handle Problem Language Result Execution time Memory
864786 2023-10-23T15:30:28 Z andrei_boaca Carnival Tickets (IOI20_tickets) C++17
27 / 100
 382 ms 60344 KB 
#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll ans=0;
int n,m;
vector<vector<int>> sol,v;
int nr1[1505],take[1505],my0[1505],my1[1505],l[1505],r[1505];
bool comp(pll a, pll b)
{
    return a.second>b.second;
}
bool by1(int a,int b)
{
    return nr1[a]>nr1[b];
}
bool bytake(int a,int b)
{
    return my1[a]>my1[b];
}
long long find_maximum(int k, std::vector<std::vector<int>> vectoras) {
	n = vectoras.size();
	m = vectoras[0].size();
	sol=vectoras;
    v=vectoras;
    bool sub3=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            sol[i][j]=-1;
            if(v[i][j]>1)
                sub3=0;
        }
    if(k==1)
    {
        vector<pll> a;
        for(int i=0;i<n;i++)
        {
            sol[i][0]=0;
            ans-=v[i][0];
            a.push_back({i,v[i][m-1]+v[i][0]});
        }
        sort(a.begin(),a.end(),comp);
        for(int i=0;i<n/2;i++)
        {
            ll poz=a[i].first;
            ans+=v[poz][0]+v[poz][m-1];
            sol[poz][0]=-1;
            sol[poz][m-1]=0;
        }
        allocate_tickets(sol);
        return ans;
    }
    if(sub3)
    {
        vector<int> linii;
        for(int i=0;i<n;i++)
        {
            linii.push_back(i);
            for(int j=0;j<m;j++)
                nr1[i]+=v[i][j];
        }
        sort(linii.begin(),linii.end(),by1);
        int suma=0;
        for(int i:linii)
        {
            int val=min(nr1[i],k);
            val=min(val,k*n/2-suma);
            take[i]=val;
            suma+=val;
        }
        reverse(linii.begin(),linii.end());
        suma=0;
        for(int i:linii)
        {
            int val=min(m-nr1[i],k-take[i]);
            val=min(val,k*n/2-suma);
            suma+=val;
            int lft=k-take[i]-val;
            take[i]+=lft;
        }
        for(int i=0;i<n;i++)
        {
            ans+=take[i];
            my1[i]=take[i];
            my0[i]=k-take[i];
            l[i]=0;
            r[i]=m-1;
        }
        if(ans>k*n/2)
        {
            int dif=ans-k*n/2;
            ans-=2*dif;
        }
        for(int pas=0;pas<k;pas++)
        {
            linii.clear();
            for(int i=0;i<n;i++)
                linii.push_back(i);
            sort(linii.begin(),linii.end(),bytake);
            int p1=-1,p0=n;
            for(int z=0;z<n;z++)
            {
                int i=linii[z];
                if(my1[i]>0)
                    p1=max(p1,z);
                if(my0[i]>0)
                    p0=min(p0,z);
            }
            if(p1<n/2-1)
            {
                for(int z=0;z<n;z++)
                {
                    int i=linii[z];
                    if(i<=p1)
                    {
                        my1[i]--;
                        sol[i][r[i]]=pas;
                        r[i]--;
                    }
                    else
                    {
                        my0[i]--;
                        sol[i][l[i]]=pas;
                        l[i]++;
                    }
                }
                continue;
            }
            if(p0>n/2)
            {
                for(int z=0;z<n;z++)
                {
                    int i=linii[z];
                    if(i>p0)
                    {
                        my1[i]--;
                        sol[i][r[i]]=pas;
                        r[i]--;
                    }
                    else
                    {
                        my0[i]--;
                        sol[i][l[i]]=pas;
                        l[i]++;
                    }
                }
                continue;
            }
            for(int z=0;z<n;z++)
            {
                int i=linii[z];
                if(i<n/2)
                {
                    my1[i]--;
                    sol[i][r[i]]=pas;
                    r[i]--;
                }
                else
                {
                    my0[i]--;
                    sol[i][l[i]]=pas;
                    l[i]++;
                }
            }
            continue;
        }
        allocate_tickets(sol);
        return ans;
    }
	return 1;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 15 ms 2716 KB Output is correct
6 Correct 382 ms 60344 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Contestant returned 4 while correct return value is 6.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 348 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 348 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 15 ms 2716 KB Output is correct
12 Correct 382 ms 60344 KB Output is correct
13 Incorrect 0 ms 348 KB Contestant returned 4 while correct return value is 6.
14 Halted 0 ms 0 KB -