USACO 2013 November Contest, Silver Problem 1. Farmer John has no Large Brown Cow

http://www.usaco.org/index.php?page=viewproblem2&cpid=343

Tips : binary Search

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

typedef long long LL;
const int MAX_N = 106;
const int MAX_K = 26;

struct P {
 int n;
 int id;
 string a[MAX_K];
} p[MAX_N],ans;

bool operator<(const P &p1,const P &p2) {
// assert(p1.n == p2.n);
 int n=p1.n;
 for(int x=0;n>x;x++) {
     if (p1.a[x] < p2.a[x]) return true;
     else if (p1.a[x] > p2.a[x]) return false;
    }
 return false;
}

vector<string> mp[MAX_N];

int main () {
 if (fopen("nocow.in","r")) {
     freopen("nocow.in","r",stdin);
     freopen("nocow.out","w",stdout);
    }
 int n,k;
 while (scanf("%d %d",&n,&k) != EOF) {
     string s;
     int m;
     getchar();
     for (int x=0;n>x;x++) {
         getline(cin,s);
         int sz=s.size();
         string i="";
         int cnt=0;
         for (int y=19;sz-4>y;y++) {
             if (s[y] == ' ') {
//                 cout<<"get "<<i<<endl;
                 mp[cnt].push_back(i);
                 p[x].a[cnt++]=i;
                 i="";
                }
             else {
                 i+= " ";
                 i[i.size()-1]=s[y];
                }
            }
         p[x].n=cnt;
         m=cnt;
        }
     LL tot=1;
     string INF = " ";
     INF[0] = 'z'+1;
     for (int x=0;m>x;x++) {
         mp[x].push_back("A");
         mp[x].push_back(INF);
         sort(mp[x].begin(),mp[x].end());
         mp[x].resize(unique(mp[x].begin(),mp[x].end()) - mp[x].begin());
         tot *= (mp[x].size() - 2);
//         for (int y=1;mp[x].size()-2>=y;y++) cout<<mp[x][y]<<' ';
//         cout<<endl;
        }
     sort(p,p+n);
     p[n].a[0] = "}";
     p[n].id = n+1;
     for (int x=0;n>x;x++) {
         p[x].id = x+1;
        }
     ans.n=m;
     for (int x=0;m>x;x++) {
         ans.a[x] = INF;
        }
     LL ss=0;
     for (int x=0;m>x;x++) {

         tot/=(mp[x].size()-2);
//         cout<<"tot = "<<tot<<endl;
//         cout<<"ss = "<<ss<<endl;
         int L=0,R=mp[x].size()-1;
         while (R-L!=1) {
             int mid=(L+R)>>1;
             ans.a[x] = mp[x][mid];
//             cout<<"mid = "<<mid<<endl;
             P tmp=*lower_bound(p,p+n,ans);
             int delta=1;
             if (!(tmp<ans) && ! (ans<tmp) ) delta = 0;
//             cout<<"val = "<<ss + (mid)*tot - (tmp).id + delta<<endl;
             if (ss + (mid)*tot - (tmp).id + delta>= k) R=mid;
             else L=mid;
            }
         ss += (R-1)*tot;
         ans.a[x] = mp[x][R];
        }
     for (int x=0;m>x;x++) {
         if (x!=0) cout<<' ';
         cout<<ans.a[x];
        }
     cout<<endl;
    }
}