Guest User

Untitled

a guest
Feb 20th, 2018
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:65777216")
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <iostream>
  5. #include <string>
  6. #include <string.h>
  7. #include <vector>
  8. #include <queue>
  9. #include <stack>
  10. #include <map>
  11. #include <set>
  12. #include <time.h>
  13. #include <cmath>
  14. #include <algorithm>
  15. #include <malloc.h>
  16.  
  17. #define pb push_back
  18. #define mp make_pair
  19. #define fi first
  20. #define se second
  21. #define sz(x) ((int) (x).size())
  22. #define forn(var, lim) for(int var=0; var<lim; ++var)
  23. #define all(x) (x).begin(), (x).end()
  24. #define abs(x) ((x)>=0 ? (x) : -(x))
  25.  
  26.  
  27. using namespace std;
  28.  
  29. typedef long long ll;
  30. typedef pair<int, int> ii;
  31. typedef vector<int> vi;
  32. typedef vector<bool> vb;
  33. typedef vector<ii> vii;
  34. typedef vector<vi> vvi;
  35. typedef vector<vb> vvb;
  36.  
  37.  
  38.  
  39. struct she{
  40.     int x, num;
  41. };
  42.  
  43. struct team{
  44.     int x, num, sh;
  45. };
  46.  
  47. bool inline operator < (she a, she b) {
  48.     return a.x<b.x;
  49. }
  50.  
  51. bool inline operator < (team a, team b) {
  52.     return a.x<b.x;
  53. }
  54.  
  55. int main(int argc, char **argv) {
  56.     int n, m;
  57.  
  58.     scanf("%d", &n);
  59.     team* b=new team[n];
  60.     forn(i, n) {
  61.         scanf("%d", &b[i].x);
  62.         b[i].num=i;
  63.     }
  64.     sort(b, b+n);
  65.  
  66.     scanf("%d", &m);
  67.     she* a=new she[m];
  68.     forn(i, m) {
  69.         scanf("%d", &a[i].x);
  70.         a[i].num=i;
  71.     }
  72.     sort(a, a+m);
  73.     vvi c(n);
  74.  
  75.     forn(i, n) {
  76.         b[i].sh=a[i].num;
  77.         c[i].pb(i);
  78.     }
  79.     for(int i=m; i<n; i++) {
  80.         b[i].sh=a[m-1].num;
  81.         ll cmax=0;
  82.         int ind;
  83.         ll ct=0;
  84.         for(int k=m-1; k>0 && c[k].size()==1;k--) {
  85.             ct+=abs(b[c[k][0]].x-a[k].x)-abs(b[c[k][0]].x-a[k-1].x);
  86.             if(ct>cmax) {
  87.                 cmax=ct;
  88.                 ind=k;
  89.             }
  90.         }
  91.         if(cmax>0) {
  92.             for(int k=ind; k<m; k++) {
  93.                 b[c[k][0]].sh=a[k-1].num;
  94.                 c[k-1].pb(c[k][0]);
  95.                 c[k].clear();
  96.             }
  97.         }
  98.         c[m-1].pb(i);
  99.     }
  100.     ll ans=0;
  101.     vi res(n);
  102.     forn(i, m) {
  103.         forn(j, c[i].size()) {
  104.             ans+=abs(b[c[i][j]].x-a[i].x);
  105.             res[b[c[i][j]].num]=a[i].num;
  106.         }
  107.     }
  108.     cout << ans << endl;
  109.     forn(i, n) {
  110.         if(i) printf(" ");
  111.         printf("%d", res[i]+1);
  112.     }
  113.     printf("\n");
  114.     return 0;
  115. }
Add Comment
Please, Sign In to add comment