oj.uz

Submission #302055

# Submission time Handle Problem Language Result Execution time Memory
302055 2020-09-18T11:56:56 Z joseacaz Carnival Tickets (IOI20_tickets) C++17
11 / 100
 2 ms 768 KB 
#include "tickets.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

ll find_maximum(int k, vector<vi> a) {
	int N = a.size();
	int M = a[0].size();
	vector<vi> answer(N, vi(M, -1));
    vpi nums;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            nums.pb({a[i][j], i*M+j});
    sort(all(nums));
    auto maxim = nums[nums.size()/2];
    vi small(N), big(N);
    int smallP = 0, bigP = N;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(a[i][j] < maxim.first)
                small[i]++;
            else if(a[i][j] == maxim.first && i*M+j < maxim.second)
                small[i]++;
        }
        big[i] = M - small[i];
        if(small[i] == 0)
            smallP++;
        else if(big[i] == 0)
            bigP--;
    }
    vi aux;
    for(int i = 0; i < N; i++)
        aux.pb(i);
    sort(all(aux), [=](int a, int b) {
            return small[a] < small[b];
        });

    ll ans = 0;
    for(int round = 0; round < k; round++)
    {
        for(int i = smallP; i < N/2; i++)
        {
            answer[aux[i]][round] = round;
            ans -= a[aux[i]][round];
        }
        for(int i = bigP; i < N; i++)
        {
            answer[aux[i]][round] = round;
            ans -= a[aux[i]][round];
        }
        for(int i = N/2; i < bigP; i++)
        {
            answer[aux[i]][M-1 - round] = round;
            ans += a[aux[i]][M-1 - round];
        }
        for(int i = 0; i < smallP; i++)
        {
            answer[aux[i]][M-1 - round] = round;
            ans += a[aux[i]][M-1 - round];
        }
    }
    
    allocate_tickets(answer);
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 768 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 256 KB Contestant returned 2235445041 while correct return value is 2727881086.
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 4 but the tickets gives a total value of 0
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Contestant returned 11 but the tickets gives a total value of -17
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 but the tickets gives a total value of -17
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Contestant returned 11 but the tickets gives a total value of -17
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Incorrect 1 ms 256 KB Contestant returned 2235445041 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -