Facebook Hacker Cup 2012 Round 1 – Recover the Sequence

#include <iostream>
#include <sstream>
#include <utility>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define MP          make_pair
#define S           size()
typedef long long   LL;

int n, its;
string s;

vector<int> merge2(vector<int> arr1, vector<int> arr2){
   vector<int> result;
   int i=0, j=0;
   while(i < arr1.size() && j < arr2.size()) {
      if(s[its] == '1') result.PB(arr1[i++]);
      else result.PB(arr2[j++]);
      its++;
   }
   while(i < arr1.size()) result.PB(arr1[i++]);
   while(j < arr2.size()) result.PB(arr2[j++]);
   return result;
}

vector<int> reverse_sort(vector<int> arr){
   int k = arr.size();
   if(k <= 1) return arr;
   int mid = int(k/2);
   vector<int> first_half, second_half;
   F(i, mid) first_half.PB(arr[i]);
   FOR(i, mid, arr.S) second_half.PB(arr[i]);
   first_half = reverse_sort(first_half);
   second_half = reverse_sort(second_half);
   return merge2(first_half, second_half);
}

int checksum(vector<int> arr) {
    int result = 1;
    for(int i=0; i<arr.size() ;i++)
       result = (31 * result + arr[i]) % 1000003;
    return result;
}

vector<int> solve(){
   vector<int> v(n), r(n);
   F(i, n) v[i] = i;
   v = reverse_sort(v);
   F(i, n) r[ v[i] ] = i+1;
   return r;
}

int main(){
   //freopen("a.in", "r", stdin);
   //freopen("recover_the_sequence.txt", "r", stdin); freopen("a.out", "w", stdout);
   int t;
   scanf("%d", &t);
   F(cas, t){
      cin>>n>>s;
      its = 0;
      printf("Case #%d: %dn", cas+1, checksum(solve()));
   }
}

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s