ural 1144. The Emperor's Riddle

  1 /**
  2 Create By yzx - stupidboy
  3 */
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <deque>
  9 #include <vector>
 10 #include <queue>
 11 #include <iostream>
 12 #include <algorithm>
 13 #include <map>
 14 #include <set>
 15 #include <ctime>
 16 #include <iomanip>
 17 using namespace std;
 18 typedef long long LL;
 19 typedef double DB;
 20 #define MIT (2147483647)
 21 #define INF (1000000001)
 22 #define MLL (1000000000000000001LL)
 23 #define sz(x) ((int) (x).size())
 24 #define clr(x, y) memset(x, y, sizeof(x))
 25 #define puf push_front
 26 #define pub push_back
 27 #define pof pop_front
 28 #define pob pop_back
 29 #define ft first
 30 #define sd second
 31 #define mk make_pair
 32 
 33 inline int Getint()
 34 {
 35     int Ret = 0;
 36     char Ch = ‘ ‘;
 37     bool Flag = 0;
 38     while(!(Ch >= ‘0‘ && Ch <= ‘9‘))
 39     {
 40         if(Ch == ‘-‘) Flag ^= 1;
 41         Ch = getchar();
 42     }
 43     while(Ch >= ‘0‘ && Ch <= ‘9‘)
 44     {
 45         Ret = Ret * 10 + Ch - ‘0‘;
 46         Ch = getchar();
 47     }
 48     return Flag ? -Ret : Ret;
 49 }
 50 
 51 const int N = 10010, M = 1010;
 52 int n, m, k, arr[N];
 53 priority_queue<pair<int, int> > index, boxes;
 54 int sum[M], belong[N], tag[N];
 55 int tmp[N];
 56 int type[2][M], ranks[M], to[M];
 57 
 58 inline void Input()
 59 {
 60     scanf("%d%d%d", &n, &m, &k);
 61     for(int i = 1; i <= n; i++) scanf("%d", &arr[i]);
 62 }
 63 
 64 inline int Check()
 65 {
 66     for(int i = 1; i <= m; i++) sum[i] = 0;
 67     for(int i = 1; i <= n; i++) sum[belong[i]] += arr[i];
 68     int mx = -INF, mn = INF;
 69     for(int i = 1; i <= m; i++)
 70         mx = max(mx, sum[i]),
 71         mn = min(mn, sum[i]);
 72     return (mx - mn) - k;
 73 }
 74 
 75 inline bool Compare(int t, int a, int b)
 76 {
 77     return type[t][a] < type[t][b];
 78 }
 79 
 80 inline bool CmpUp(int a, int b)
 81 {
 82     return Compare(0, a, b);
 83 }
 84 
 85 inline bool CmpDown(int a, int b)
 86 {
 87     return Compare(1, b, a);
 88 }
 89 
 90 inline void Solve()
 91 {
 92     srand(time(0));
 93     //sort(arr + 1, arr + 1 + n, greater<int>() );
 94     for(int i = 1; i <= m; i++) index.push(mk(-sum[i], i));
 95     for(int i = 1; i <= n; i++) boxes.push(mk(arr[i], i));
 96     for(int i = 1; i <= n; i++)
 97     {
 98         int u = index.top().sd, v = boxes.top().sd;
 99         index.pop(), boxes.pop();
100         sum[u] += arr[v], belong[v] = u;
101         index.push(mk(-sum[u], u));
102     }
103 
104     int now;
105     while((now = Check()) > 0)
106     {
107         //printf("%d\n", now);
108         for(int i = 1; i <= n; i++)
109             tag[i] = rand() & 1;
110 
111         for(int t = 0; t < 2; t++)
112             for(int i = 1; i <= m; i++)
113                 type[t][i] = 0;
114         for(int i = 1; i <= n; i++)
115             type[tag[i]][belong[i]] += arr[i];
116 
117         for(int t = 0; t < 2; t++)
118         {
119             for(int i = 1; i <= m; i++)
120                 ranks[i] = i;
121             if(t == 0)
122                 sort(ranks + 1, ranks + 1 + m, CmpUp);
123             else sort(ranks + 1, ranks + 1 + m, CmpDown);
124 
125             for(int i = 1; i <= m; i++) to[ranks[i]] = i;
126             for(int i = 1; i <= n; i++)
127                 if(tag[i] == t)
128                     tmp[i] = to[belong[i]];
129         }
130 
131         for(int i = 1; i <= n; i++)
132             belong[i] = tmp[i];
133     }
134 
135     int ans = Check() + k;
136     printf("%d\n", ans);
137     vector<int> answer[M];
138     for(int i = 1; i <= n; i++) answer[belong[i]].pub(i);
139     for(int i = 1; i <= m; i++)
140     {
141         int length = sz(answer[i]);
142         for(int j = 0; j < length - 1; j++)
143             printf("%d ", answer[i][j]);
144         if(length) printf("%d\n", answer[i].back());
145         /*int p = 0;
146         for(int j = 0; j < length - 1; j++)
147         {
148             printf("%d ", arr[answer[i][j]]);
149             p += arr[answer[i][j]];
150         }
151         if(length)
152         {
153             printf("%d ", arr[answer[i].back()]);
154             p += arr[answer[i].back()];
155         }
156         printf("%d\n", p);*/
157     }
158     //sfor(int i = 1; i <= m; i++) printf("%d ", sum[i]);
159 }
160 
161 int main()
162 {
163     freopen("a.in", "r", stdin);
164     freopen("a.out", "w", stdout);
165     Input();
166     Solve();
167     return 0;
168 }