fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct W {
  5.     long long a, b, c;
  6.     int idx; // 0-based index
  7. };
  8.  
  9. int main() {
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.  
  13.     int n;
  14.     if (!(cin >> n)) return 0;
  15.     vector<W> w(n);
  16.     for (int i = 0; i < n; ++i) {
  17.         cin >> w[i].a >> w[i].b >> w[i].c;
  18.         w[i].idx = i;
  19.     }
  20.  
  21.     vector<char> canBeat(n, false);
  22.  
  23.     // Pass 1: check (a_j < a_i) and (b_j < b_i)
  24.     {
  25.         auto v = w;
  26.         sort(v.begin(), v.end(), [](const W& x, const W& y){
  27.             if (x.a != y.a) return x.a < y.a;
  28.             return x.b < y.b; // tie-breaker not essential
  29.         });
  30.         long long bestB = LLONG_MAX; // min b among strictly smaller a's
  31.         for (int i = 0; i < n; ) {
  32.             int j = i;
  33.             long long groupMinB = LLONG_MAX;
  34.             while (j < n && v[j].a == v[i].a) {
  35.                 if (bestB < v[j].b) canBeat[v[j].idx] = true;
  36.                 groupMinB = min(groupMinB, v[j].b);
  37.                 ++j;
  38.             }
  39.             bestB = min(bestB, groupMinB);
  40.             i = j;
  41.         }
  42.     }
  43.  
  44.     // Pass 2: check (a_j < a_i) and (c_j < c_i)
  45.     {
  46.         auto v = w;
  47.         sort(v.begin(), v.end(), [](const W& x, const W& y){
  48.             if (x.a != y.a) return x.a < y.a;
  49.             return x.c < y.c;
  50.         });
  51.         long long bestC = LLONG_MAX; // min c among strictly smaller a's
  52.         for (int i = 0; i < n; ) {
  53.             int j = i;
  54.             long long groupMinC = LLONG_MAX;
  55.             while (j < n && v[j].a == v[i].a) {
  56.                 if (bestC < v[j].c) canBeat[v[j].idx] = true;
  57.                 groupMinC = min(groupMinC, v[j].c);
  58.                 ++j;
  59.             }
  60.             bestC = min(bestC, groupMinC);
  61.             i = j;
  62.         }
  63.     }
  64.  
  65.     // Pass 3: check (b_j < b_i) and (c_j < c_i)
  66.     {
  67.         auto v = w;
  68.         sort(v.begin(), v.end(), [](const W& x, const W& y){
  69.             if (x.b != y.b) return x.b < y.b;
  70.             return x.c < y.c;
  71.         });
  72.         long long bestC = LLONG_MAX; // min c among strictly smaller b's
  73.         for (int i = 0; i < n; ) {
  74.             int j = i;
  75.             long long groupMinC = LLONG_MAX;
  76.             while (j < n && v[j].b == v[i].b) {
  77.                 if (bestC < v[j].c) canBeat[v[j].idx] = true;
  78.                 groupMinC = min(groupMinC, v[j].c);
  79.                 ++j;
  80.             }
  81.             bestC = min(bestC, groupMinC);
  82.             i = j;
  83.         }
  84.     }
  85.  
  86.     // Collect warriors that cannot beat anyone
  87.     vector<int> ans;
  88.     for (int i = 0; i < n; ++i)
  89.         if (!canBeat[i]) ans.push_back(i + 1); // 1-based indices
  90.  
  91.     cout << ans.size() << "\n";
  92.     for (int i = 0; i < (int)ans.size(); ++i) {
  93.         if (i) cout << ' ';
  94.         cout << ans[i];
  95.     }
  96.     if (!ans.empty()) cout << '\n';
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
3
700 40 1
50 2 800
3 900 60
stdout 
0
https://ideone.com/ux5fLb
language:
C++14 (gcc 8.3)
created:
15 days 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!