Submission #1198692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198692		LucaLucaM	Carnival Tickets (IOI20_tickets)	C++20	100 / 100	583 ms	62240 KiB

tickets

#include "tickets.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>

using ll = long long;

struct Change {
  int delta, i;
  bool operator < (const Change &other) const {
    return delta > other.delta;
  };
};

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

  std::vector<std::vector<int>> answer(n, std::vector<int>(m, -1));
  
  std::vector<int> cntneg(n, k);
  std::vector<int> cntpos(n, 0);

  ll sum = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++) {
      sum += -a[i][j];
    }
  }

  std::vector<Change> deltas;
  for (int i = 0; i < n; i++) {
    for (int alcatelea = 1; alcatelea <= k; alcatelea++) {
      int apare = m - alcatelea;
      int dispare = k - alcatelea;
      deltas.push_back({a[i][apare] + a[i][dispare], i});
    }
  }

  std::sort(deltas.begin(), deltas.end());

  assert((int) deltas.size() >= n * k / 2);

  for (int i = 0; i < n * k / 2; i++) {
    auto [increase, row] = deltas[i];
    sum += increase;
    cntpos[row]++;
    cntneg[row]--;
  }

  for (int round = 0; round < k; round++) {
    std::vector<int> rows;
    for (int i = 0; i < n; i++) {
      rows.push_back(i);
    }
    std::sort(rows.begin(), rows.end(), [&](int x, int y) {
      return cntpos[x] > cntpos[y];
    });
    for (int i = 0; i < n / 2; i++) {
      assert(cntpos[rows[i]] >= 0);
      answer[rows[i]][m - cntpos[rows[i]]--] = round; 
    }
    for (int i = n / 2; i < n; i++) {
      assert(cntneg[rows[i]] >= 1);
      answer[rows[i]][--cntneg[rows[i]]] = round;
    }
  }
  
  allocate_tickets(answer);

  return sum;
}

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