• If you run the count for the full size of a answer, it might be very large.
  • One input has 10,001 inputs all with value 1,000,000
  • So this will time out if you are not careful
  • A mod by the size of the people left will fix this.
  • But you need to be careful, if you have a result of 0, it needs to be set back to the size of the list. (you never have a 1 0r 0, so you will count to the end).

• count = j->count % people.size();
  if (count == 0) {
       count = people.size();
  } 

struct Person{
    Person(int i, int c) {
      id = i;
      count = c;
    }
    int id;
    int count;
}; 

#include <list>
list <Person> people;
typedef list::iterator  peopIt; 

• It even returns a pointer to the next item in the list.

void Fix(peopIt &  j) {
    if (j == people.end()) {
       j  = people.begin();
    }
} 

• But I did not know about this so I wrote a simple program.

• #include <iostream>
  #include <algorithm>
  #include <vector>
  
  using namespace std;
  
  class Judge{
      public:
      Judge(int i, long double d) {
          id = i;
          distance = d;
      }
  
      bool operator <(const Judge & other) {
          return distance > other.distance;
      }
  
      void Tell() {
         cout << id << " " << distance;
      }
      private:
          int id;
          long double distance;
  };
  
  int main() {
      vector<Judge> people;
  
      srand(time(nullptr));
  
      for (int i=0;i<10;i++) {
         people.push_back(Judge(i,rand()%20));
      }
  
      make_heap(people.begin(), people.end());
  
      while (people.size() > 0) {
         people.front().Tell();
         cout << endl;
         pop_heap(people.begin(), people.end());  people.pop_back();
      }
  } 

• The code is here
• Not too bad, it seems to work.

• Build a judge class

  • struct Judge {
        Judge(int xc, int yc) {
           x = xc;
           y = yc;
        }
        int x, y;
    }; 

  • I read all of my judges in to start

  • int main() {
        int judges, tars, feathers;
        long double totalDistance = 0;
        vector <Judge> judgeList;
    
        cin >> judges >> tars >> feathers;
    
        for (int i=0;i> x >>y;
            judgeList.push_back(Judge(x,y));
        } 
    
        totalDistance =  ProcessItem(judgeList, tars);
        totalDistance += ProcessItem(judgeList, feathers);
    
        cout  << fixed << setprecision(6);
        cout << totalDistance  << endl;
    
        return 0;
    } 

• And a Place class

  • struct Place{
        Place(int j, int i, long double d) {
            id = i;
            judge = j;
            distance = d;
        }
    
        long double distance;
        int judge;
        int id;
    
        bool operator  < (const Place & other) {
            if (distance == other.distance) {
                if (judge == other.judge) {
                   return id > other.id;
                } else {
                   return judge > other.judge;
                }
            } else {
                return distance > other.distance;
            }
        }
    }; 

  • Notice, the less than operator
    • Incorporates all of the comparison rules
    • Has all things reversed, it is really a greater than.
    • But the heap is a max heap, so ...
• Process the tar and feather items the same, so I built (refactored) into a function.

  • long double ProcessItem( vector & judgeList, int count) {
        int i;
        vector <Place> pits;
        int judgesFound = 0;
        long double totalDistance = 0; 

  • Build an array of bools for the item and the judges.
    • Initialize them to false.
    • Set to true when a judge or an item is used.

    •     vector<bool> pitUsed(count, false);
          vector<bool> judgeUsed(judgeList.size(),false); 

  • Read in the pit locations and compute the distance from each judge to each pit.

  •     for(int i=0;<count; i++) {
            int x,y;
            long double distance;
            cin >> x >> y;
            for (int j=0; j<judgeList.size();j++) {
                distance = Distance(judgeList[j].x, judgeList[j].y, x,y);
                pits.push_back(Place(j,i,distance));
            }
        } 

  • Then build the heap

  • make_heap(pits.begin(), pits.end());
    	

  • Finally, find a match for each judge, computing the distance as we go

  •     while (pits.size()  > 0 and judgesFound < judgeList.size()) {
           int j = pits.front().judge;
           int p = pits.front().id;
    
           if (!judgeUsed[j] and !pitUsed[p]) {
               totalDistance += pits.front().distance;
               judgeUsed[j] = true;
               pitUsed[p] = true;
               judgesFound ++;
           }
           pop_heap(pits.begin(), pits.end());  pits.pop_back();
        } 

• My code

• I thought there might be an underlying trick to this one,
  • But I didn't know it
  • So I decided to brute force it.
• One input

  n = 1000000 m = 1377387113  a = 1377387114 c = 169365001  x0 = 123456 

• You need one trick
  • (a+b)% c = (a%c + b%c)%c
• I implemented binary search
• < pre class="prettyprint"> bool Bsearch(long key, const vector & seq, int start, int stop) { if (start > stop) { return false; } int mid = (start + stop) / 2; if (seq[mid] == key) { return true; } if (seq[mid] < key) { return (Bsearch(key, seq, mid+1, stop)); } else { return (Bsearch(key, seq, start, mid-1)); } }
• Generated all elements in the sequence needed

•     cin >> n >> m >> a >> c >> x0;
  
      vector seq;
  
      long xOld = x0;
      long xNew;
  
      for(int i=0;i<n;i++) {
          xNew =  ((xOld * a) %m  + c) % m;
          seq.push_back(xNew);
          xOld = xNew;
      } 

• Then counted the number of times the search works.

• int count = 0;
  for(auto x: seq) {
      if (Bsearch(x,seq,0, seq.size()-1)) {
         count ++;
      }
  } 

• Worked on all test cases in .08 sec., so good enough.
• My Code