fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. class Cloth{
  6. public:
  7.     int claps;
  8.     int id;
  9.     int complet;
  10.  
  11.     Cloth (int claps, int id, int complet){
  12.         this->claps = claps;
  13.         this->id = id;
  14.         this->complet = complet;
  15.     }
  16.  
  17.     bool operator <(const Cloth & c) const{
  18.         if (this->claps == c.claps)
  19.             return this->id > c.id;
  20.         else
  21.             return this->claps < c.claps;
  22.     }
  23. };
  24.  
  25. priority_queue<Cloth> pq;
  26. vector<int> colors;
  27. vector<int> days;
  28. vector<int> seen(1e6 + 7, 0);
  29.  
  30. void load_days(int n){
  31.     days.resize(n);
  32.     for (int i = 0; i < n; i++){
  33.         cin >> days[i];
  34.         pq.push(Cloth(days[i] * 5, i, 3));
  35.         pq.push(Cloth(days[i] * 3, i, 2));
  36.         pq.push(Cloth(days[i] * 2, i, 1));
  37.     }
  38. }
  39.  
  40. void load_colors(int k){
  41.     colors.resize(k);
  42.     for (int i = 0; i < k; i++){
  43.         cin >> colors[i];
  44.     }
  45. }
  46.  
  47. int find_min_use_claps(int k){
  48.     vector<int> last_complet;
  49.     int pointer = 0;
  50.  
  51.     while (!pq.empty()){
  52.         Cloth cloth = pq.top();
  53.         pq.pop();
  54.  
  55.         if (seen[cloth.id] == 3 || (cloth.complet == 2 && seen[cloth.id] == 2))
  56.             continue;
  57.  
  58.         if (pointer == k)
  59.             return -1;
  60.  
  61.         if (cloth.claps <= colors[pointer]){
  62.             if (cloth.complet == 3)
  63.                 last_complet.push_back(cloth.id);
  64.             seen[cloth.id] += cloth.complet;
  65.             pointer++;
  66.         }
  67.         else if (cloth.complet != 3){ //jesli jest zbyt malo dla koszulek lub skarpetek 
  68.             if (last_complet.empty()){
  69.                 return - 1;
  70.             }
  71.             else{ //jesli wczesniej byl moment gdzie koszulki i skarpetki dalismy do jednego koloru to w to miejsce dajemy aktualne ubranie
  72.                 int last_id = last_complet[last_complet.size()-1];
  73.                 seen[last_id] = 0;
  74.                 pq.push(Cloth(days[last_id] * 3, last_id, 2)); // dajemy na kolejke koszulki i skarpetki tej osoby u ktorej one sa powieszone na jednym kolorze
  75.                 pq.push(Cloth(days[last_id] * 2, last_id, 1));
  76.                 last_complet.pop_back();
  77.             }
  78.         }
  79.  
  80.     }
  81.     return pointer;
  82. }
  83.  
  84. int main(){
  85.     ios::sync_with_stdio(0);
  86.     cin.tie(NULL);
  87.  
  88.     int n, k;
  89.     cin >> n >> k;
  90.  
  91.     load_days(n);
  92.  
  93.     load_colors(k);
  94.  
  95.     sort(colors.begin(), colors.end(), greater<int>());
  96.  
  97.     int response = find_min_use_claps(k);
  98.  
  99.     if (response == -1)
  100.         cout << "NIE\n";
  101.     else
  102.         cout << response << "\n";
  103.  
  104.     return 0;
  105. }
Success #stdin #stdout 0s 6980KB
comments (?)
stdin
copy 
2 4

10 7

35 20 21 14
stdout
copy 
4
https://ideone.com/D2FbPt
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!