Submission #604079

#	Time	Username	Problem	Language	Result	Execution time	Memory
604079		Sam_a17	Carnival Tickets (IOI20_tickets)	C++14	11 / 100	1 ms	724 KiB

tickets

// #include "A.cpp"
#include <bits/stdc++.h>
// #include <vector>
using namespace std;
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(x) cout << #x << " " << x << endl;
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
#define pb push_back
#define ld long double
#define ll long long
 
// #include "tickets.h"
// #include <vector>
 
void allocate_tickets(vector<vector<int>> a);
 
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	std::vector<std::vector<int>> answer;
//  dbg(k)
  if(m == 1) {
    vector<vector<int>> answ;
    long long pat = 0;
    vector<long long> values;
    map<long long, int> mp;
    for(int i = 0; i < n; i++) {
      answ.push_back({0});
      values.push_back(x[i][0]);
      mp[x[i][0]]++;
      pat += x[i][0];
    }
 
    sort(all(values));
 
    ll s = INT64_MAX, left = 0, leftCnt = 0;
    for(auto i: mp) {
      leftCnt += i.second;
      left += i.second * i.first;
 
      ll rightCnt = n - leftCnt;
      pat -= i.second * i.first;
 
      s = min(s, leftCnt * i.first - left + pat - rightCnt * i.first);
    }
 
  	allocate_tickets(answ);
    return s;
  }
  else if(k == 1) {
    vector< vector<pair<int, int>> > xi;
    for(int i = 0; i < n; i++) {

      vector< pair<int, int> > vi;
      for(int j = 0; j < m; j++) {
        vi.push_back({x[i][j], j});
      }
      
      sort(all(xi[i]));
    }

    ll s = 0;
    vector<int> ik(n, 1);
    for(int i = 0; i < n; i++) {
      s += xi[i].back().first;
    }

    vector<pair<ll, int>> diff;
    for(int i = 0; i < n; i++) {
      diff.push_back({x[i].back() - x[i].front(), i});
    }

    sort(all(diff));

    for(int i = 0; i < n / 2; i++) {
      s -= diff[i].first;
      int id = diff[i].second;
      ik[xi[i][id].second] = 0;
    }

    vector<int> cr;
    for(int i = 0; i < n; i++) {
      if(ik[i]) {
        cr.push_back(xi[i].back().second);
      } else {
        cr.push_back(xi[i].front().second);
      }
      cout << cr[i] << " ";
    } cout << endl;

    answer.push_back(cr);
    return s;
  }
	allocate_tickets(answer);
	return 1;
}

• 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