fork(1) download 
  1. //84104971101048411497 - Can you guess what does this mean?
  2. using namespace std;
  3. #include <bits/stdc++.h>
  4. #define mapii map<int, int>
  5. #define debug(a) cout << #a << ": " << a << endl
  6. #define fdto(i, r, l) for(int i = (r); i >= (l); --i)
  7. #define fto(i, l, r) for(int i = (l); i <= (r); ++i)
  8. #define forit(it, type, var) for(type::iterator it = var.begin(); it != var.end(); it++)
  9. #define fordit(rit, type, var) for(type::reverse_iterator rit = var.rbegin(); rit != var.rend(); rit++)
  10. #define ii pair<int, int>
  11. #define iii pair<int, ii>
  12. #define ff first
  13. #define ss second
  14. #define mp make_pair
  15. #define pb push_back
  16. #define ll long long
  17. #define maxN 15
  18. #define maxK 35
  19.  
  20. struct box {
  21.     int id, n;
  22.     int d[maxN];
  23.     inline bool operator < (const box &b) const {
  24.         fto(i, 1, n)
  25.             if (d[i] >= b.d[i]) return false;
  26.         return true;
  27.     }
  28. };
  29.  
  30. int k, n, f[maxK], trace[maxK];
  31. box a[maxK];
  32. vector<int> ans;
  33.  
  34. int main () {
  35.     #ifndef ONLINE_JUDGE
  36.         freopen("input.txt", "r", stdin);
  37.         //freopen("output.txt", "w", stdout);
  38.     #endif // ONLINE_JUDGE
  39.  
  40.     while (scanf("%d%d", &k, &n) != EOF) {
  41.         fto(i, 1, k)
  42.             fto(j, 1, n) scanf("%d", &a[i].d[j]);
  43.         fto(i, 1, k) {
  44.             a[i].id = i;
  45.             a[i].n = n;
  46.             sort(a[i].d+1, a[i].d+n+1);
  47.         }
  48.         // Good-old Bubble Sort algorithm
  49.         fto(i, 1, k-1)
  50.             fto(j, i+1, k)
  51.                 if (a[j] < a[i]) swap(a[i], a[j]);
  52.         // Printing out all boxes
  53.         fto(i, 1, k) {
  54.             printf("%d\n", a[i].id);
  55.             fto(j, 1, n) printf("%d ", a[i].d[j]);
  56.             printf("\n");
  57.         }
  58.         fto(i, 1, k) {
  59.             f[i] = 1;
  60.             trace[i] = 0;
  61.             fto(j, 1, i-1) {
  62.                 if (a[j] < a[i] && f[i] < f[j]+1) {
  63.                     f[i] = f[j]+1;
  64.                     trace[i] = j;
  65.                 }
  66.             }
  67.         }
  68.         printf("%d\n", *max_element(f+1, f+k+1));
  69.         int pos = max_element(f+1, f+k+1)-f;
  70.  
  71.         ans.clear();
  72.         int u = pos;
  73.         while (trace[u] != 0) {
  74.             u = trace[u];
  75.             ans.pb(a[u].id);
  76.         }
  77.         fordit(rit, vector<int>, ans) printf("%d ", *rit);
  78.         printf("%d\n", a[pos].id);
  79.     }
  80.  
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0s 3420KB
comments (?)
stdin 
27 2
39 26
63 17
64 46
75 13
26 25
21 45
15 22
41 41
98 92
27 81
37 65
39 25
53 50
72 55
12 42
66 65
10 96
90 90
93 77
24 70
64 49
87 79
33 99
59 11
49 43
43 31
76 85
stdout 
7
15 22 
15
12 42 
5
25 26 
24
11 59 
6
21 45 
1
26 39 
12
25 39 
8
41 41 
2
17 63 
26
31 43 
25
43 49 
13
50 53 
20
24 70 
4
13 75 
21
49 64 
17
10 96 
3
46 64 
11
37 65 
10
27 81 
14
55 72 
16
65 66 
27
76 85 
23
33 99 
19
77 93 
22
79 87 
18
90 90 
9
92 98 
11
7 5 1 8 25 13 14 27 22 18 9
https://ideone.com/sl7h1J
language:
C++ (gcc 8.3)
created:
8 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!