fork download
copy 
  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. 		// std::stable_sort algorithm
  49.         stable_sort(a+1, a+k+1);
  50.         // Printing out all boxes
  51.         fto(i, 1, k) {
  52.             printf("%d\n", a[i].id);
  53.             fto(j, 1, n) printf("%d ", a[i].d[j]);
  54.             printf("\n");
  55.         }
  56.         fto(i, 1, k) {
  57.             f[i] = 1;
  58.             trace[i] = 0;
  59.             fto(j, 1, i-1) {
  60.                 if (a[j] < a[i] && f[i] < f[j]+1) {
  61.                     f[i] = f[j]+1;
  62.                     trace[i] = j;
  63.                 }
  64.             }
  65.         }
  66.         printf("%d\n", *max_element(f+1, f+k+1));
  67.         int pos = max_element(f+1, f+k+1)-f;
  68.  
  69.         ans.clear();
  70.         int u = pos;
  71.         while (trace[u] != 0) {
  72.             u = trace[u];
  73.             ans.pb(a[u].id);
  74.         }
  75.         fordit(rit, vector<int>, ans) printf("%d ", *rit);
  76.         printf("%d\n", a[pos].id);
  77.     }
  78.  
  79.     return 0;
  80. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
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
copy 
7
15 22 
5
25 26 
1
26 39 
2
17 63 
12
25 39 
8
41 41 
15
12 42 
3
46 64 
4
13 75 
6
21 45 
24
11 59 
10
27 81 
26
31 43 
11
37 65 
16
65 66 
17
10 96 
20
24 70 
21
49 64 
22
79 87 
18
90 90 
19
77 93 
23
33 99 
25
43 49 
13
50 53 
14
55 72 
27
76 85 
9
92 98 
9
7 5 1 8 3 16 22 18 9
https://ideone.com/LaXbMR
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!