Submission #779287

#	Time	Username	Problem	Language	Result	Execution time	Memory
779287		jasmin	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	1 ms	696 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;

long long solvem1(int n, int k, vector<vector<int> >& x){

    vector<int> s(n);
    for(int i=0; i<n; i++){
        s[i]=x[i][0];
    }

    sort(s.begin(), s.end());
    int mi=s[n/2];

    long long ans=0;
    for(int i=0; i<n; i++){
        if(s[i]<mi){
            ans += mi-s[i];
        }
        else{
            ans += s[i]-mi;
        }
    }
    return ans;
}

long long solvek1(int n, int m, int k, vector<vector<int> >& x, vector<vector<int> >& answer){

    vector<int> minind(n, 0);
    vector<int> maxind(n, 0);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            
            if(x[i][j] < x[i][minind[i]]){
                minind[i]=j;
            }
            if(x[i][j] >= x[i][maxind[i]]){
                maxind[i]=j;
            }

        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            answer[i][j]=-1;
        }

        answer[i][maxind[i]]=0;
    }

    vector<pair<int,int> > sorted;
    for(int i=0; i<n; i++){
        sorted.push_back({x[i][minind[i]], i});
        sorted.push_back({x[i][maxind[i]], i});
    }
    sort(sorted.begin(), sorted.end());

    set<int> smaller;
    for(auto [num, ind]: sorted){

        smaller.insert(ind);
        answer[ind][maxind[ind]]=-1;
        answer[ind][minind[ind]]=0;

        if(smaller.size()==n/2){
            break;
        }
    }

    vector<int> nums;
    for(int i=0; i<n; i++){
        if(answer[i][maxind[i]]){
            nums.push_back(x[i][maxind[i]]);
        }
        else{
            nums.push_back(x[i][minind[i]]);
        }
    }
    sort(nums.begin(), nums.end());

    int mi=nums[n/2];
    long long ans=0;
    for(int i=0; i<n; i++){
        ans += abs(nums[i]-mi);
    }
    return ans;
}

long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();

	vector<vector<int> > answer(n, vector<int> (m, 0));
    long long ans=0;

    if(m==1){
        ans=solvem1(n, k, x);
    }
    else if(k==1){
        ans=solvek1(n, m, k, x, answer);
    }
	
    allocate_tickets(answer);
	return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int solvek1(int, int, int, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&)':
tickets.cpp:66:26: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |         if(smaller.size()==n/2){
      |            ~~~~~~~~~~~~~~^~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10