naoya_t@topcoder

SRM438 Div1 Tricky: UnluckyIntervals

05:27 |

• Easy改めTricky
• 落とし穴は解ったので書き直してみた
• luckySetはソートされて与えられると思ってたらそうでない場合があった。思い込み。
• いくつのintervalにカバーされているかのカウントが正しくなかったようで、うまくいかないケースがあったので単純な方法（掛け算して1を引く）に変更。
• 同じコードを何度も書いてたのをまとめた

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class UnluckyIntervals {
 public:
  vector<int> getLuckiest(vector<int> luckySet, int n) {
    int N=sz(luckySet);
    sort(all(luckySet)); /// してなかった

    priority_queue<pair<ll,int> > pq;
    tr(luckySet,it) pq.push(make_pair(0LL,-(*it)));

    vector<pair<ll,ll> > intervals;
    if (1<=luckySet[0]-1) intervals.pb(make_pair(1LL,(ll)luckySet[0]-1));

    rep(i,N-1) {
      int a=luckySet[i], b=luckySet[i+1];
      if (a+1<=b-1) intervals.pb(make_pair((ll)a+1,(ll)b-1));
    }
    intervals.pb(make_pair((ll)luckySet[N-1]+1, LONG_LONG_MAX));

    tr(intervals,it){
      ll a=it->first, b=it->second;
      if (a>b) continue;
      if (b==LONG_LONG_MAX){
        rep(i,n) pq.push(make_pair(-LONG_LONG_MAX,-(a+i)));
      } else if (a==b) { /// ここ(luckyの隙間に1つだけ数がある場合)を無視してた
        pq.push(make_pair(0LL,-a));
      } else {
        for(ll c=0,i=a,j=b,l=1,r=b-a+1; i<=j; i++,j--,l++,r--) {
          ll z = l*r-1;
          pq.push(make_pair(-z,-i)); c++;
          if (i!=j) { pq.push(make_pair(-z,-j)); c++; }
          if (c>n) break;
        }
      }
    }

    vi res;
    rep(i,n){
      pair<int,int> pr = pq.top(); pq.pop();
      res.pb(-pr.second);
    }
    return res;
  }
};