v 0. Pasted by slipstak2 as cpp at 2011-11-01 07:54:52 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №9. Дополнительные олимпиадные задачи
  3. // Задача B. Гражданская оборона
  4. // ibelyaev: 31Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.html
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. const int MAX_VALUE = 2e9 + 1e3;
  25. int n,m;
  26.  
  27. struct bomb_saver {
  28.     int num, val;
  29.     bomb_saver(){}
  30.     bomb_saver(int n, int v) : num(n), val(v){}
  31. };
  32. struct bs_compare {
  33.     bool operator () (const bomb_saver &a, const bomb_saver &b) {
  34.         return a.val < b.val;
  35.     }
  36.     bool operator () (bomb_saver const &a, int val) {
  37.         return a.val < val;
  38.     }
  39.     bool operator () (int val, bomb_saver const &b) {
  40.         return val < b.val;
  41.     }
  42. };
  43. vector<int> town;
  44. vector<bomb_saver> bs;
  45. void input(){
  46.     scanf("%d" ,&n);
  47.     town.resize(n);
  48.     for (int i=0;i<n;++i)
  49.         scanf("%d", &town[i]);
  50.     scanf("%d", &m);
  51.     bs.resize(m + 2);
  52.     bs[0] = bomb_saver(-1,-MAX_VALUE);
  53.     for (int i=1;i<=m;++i) {
  54.         bs[i].num = i;
  55.         scanf("%d", &bs[i].val);
  56.     }
  57.     bs.back() = bomb_saver(-1,MAX_VALUE);
  58. }
  59. void solve(){
  60.     sort(bs.begin(), bs.end(), bs_compare());
  61.     for (int i=0;i<town.size(); ++i) {
  62.         int pos = lower_bound(bs.begin(), bs.end(), town[i], bs_compare()) - bs.begin();
  63.         int lenF = bs[pos].val - town[i];
  64.         int lenB = town[i] - bs[pos-1].val;
  65.         int num = bs[pos].num;
  66.         if (lenF > lenB) num = bs[pos-1].num;
  67.             printf("%d ", num);
  68.     }
  69. }
  70. int main()
  71. {
  72.     freopen("input.txt","r",stdin);
  73.     freopen("output.txt","w",stdout);
  74.  
  75.     input();
  76.     solve();
  77.  
  78.     return 0;
  79. }


Editing is locked.