Submission #672688

#	Time	Username	Problem	Language	Result	Execution time	Memory
672688		tbzard	Carnival Tickets (IOI20_tickets)	C++14	14 / 100	937 ms	57680 KiB

tickets

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

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

    vector<vector<int> > s(n);
    vector<int> num(n);
    long long ans = 0;
    for(int i=0;i<n;i++) s[i].resize(m);   
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            s[i][j] = -1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(x[i][j]) num[i]++;
        }
    }
    for(int i=0;i<k;i++){
        vector<pair<int, int> > y;
        int rem = m-i;
        for(int j=0;j<n;j++){
            int one = num[j], zero = rem-num[j];
            y.push_back(make_pair(one-zero, j));
        }
        sort(y.begin(), y.end());
        vector<int> g0, g1;
        for(int j=0;j<n/2;j++){
            int one = (rem+y[j].first)/2;
            int zero = rem-one;
            if(zero > 0) g0.push_back(y[j].second);
            else g1.push_back(y[j].second);
        }
        for(int j=n/2;j<n;j++){
            int one = (rem+y[j].first)/2;
            int zero = rem-one;
            if(one > 0) g1.push_back(y[j].second);
            else g0.push_back(y[j].second);
        }
        if((int)g0.size() >= n/2) ans += (int)g1.size();
        else ans += (int)g0.size();
        for(int j=0;j<g0.size();j++){
            int u = g0[j];
            for(int k=0;k<m;k++){
                if(s[u][k] == -1){
                    s[u][k] = i;
                    break;
                }
            }
        }
        for(int j=0;j<g1.size();j++){
            int u = g1[j];
            num[u]--;
            for(int k=m-1;k>=0;k--){
                if(s[u][k] == -1){
                    s[u][k] = i;
                    break;
                }
            }
        }
    }
    allocate_tickets(s);
    return ans;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:39:17: warning: unused variable 'zero' [-Wunused-variable]
   39 |             int zero = rem-one;
      |                 ^~~~
tickets.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int j=0;j<g0.size();j++){
      |                     ~^~~~~~~~~~
tickets.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int j=0;j<g1.size();j++){
      |                     ~^~~~~~~~~~

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