Don't like ads? PRO users don't see any ads ;-)

Find the bug

By: LucasLima on Sep 7th, 2012  |  syntax: C++  |  size: 1.85 KB  |  hits: 27  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <fstream>
  2. #include <queue>
  3. #include <cstdlib>
  4.  
  5. using namespace std;
  6.  
  7. typedef unsigned long long int ll;
  8.  
  9. struct Run {
  10.         ifstream file;
  11.         int contador;
  12.         queue<ll> buffer;
  13.         bool valid;
  14. };
  15.  
  16. const long totalSize = 12500000*8;
  17. const long bufferSize = 12500000/8;
  18. const int numberRuns = 8;
  19. Run runs[numberRuns];
  20.  
  21. long count = 0;
  22.  
  23. ifstream input("runs.bin", ios::in | ios::binary);
  24. ofstream output("sorted.bin", ios::out | ios::binary);
  25.  
  26. void start() {
  27.         for (int i = 0; i < numberRuns; ++i) {
  28.                 for (int j = 0; j < bufferSize; ++j) {
  29.                         ll x;
  30.                         runs[i].file.read((char*)&x, sizeof(ll));
  31.                         runs[i].buffer.push(x);
  32.                         ++count;
  33.                 }
  34.         }
  35. }
  36.  
  37. int teste = 0;
  38.  
  39. int main () {
  40.         for (long i = 0; i < numberRuns; ++i) {
  41.                 runs[i].file.open("runs.bin", ios::in | ios::binary);
  42.                 runs[i].file.seekg((i*12500000)*sizeof(ll));
  43.                 runs[i].contador = 0;
  44.                 runs[i].valid = true;
  45.         }
  46.         start();
  47.         for (long k = 0; k < totalSize; ++k) {
  48.                 ll smaller = -10000; int aux = 0;
  49.                 for (int j = 0; j < numberRuns; ++j) {
  50.                         if (runs[j].valid) {
  51.                                 if (runs[j].buffer.front() < smaller) {
  52.                                         smaller = runs[j].buffer.front();
  53.                                         aux = j;
  54.                                 }
  55.                         }
  56.                 }
  57.                 runs[aux].buffer.pop();
  58.                 if (runs[aux].buffer.empty()) {
  59.                         for (int j = 0; j < bufferSize; ++j) {
  60.                                 ll x;
  61.                                 runs[aux].file.read((char*)&x, sizeof(ll));
  62.                                 runs[aux].buffer.push(x);
  63.                                 ++count;
  64.                         }
  65.                         if (++runs[aux].contador == (numberRuns - 1)) runs[aux].valid = false;
  66.                         //printf("%d %d %d\n", ++teste, aux, runs[aux].contador);
  67.                 }
  68.                 /*printf("aux %d", aux);
  69.                 system("PAUSE");*/
  70.                 output.write((char*)&smaller, sizeof(ll));
  71.         }
  72.         for (int i = 0; i < numberRuns; ++i) {
  73.                 if (!runs[i].buffer.empty()) { printf("%d %lld\n", i, runs[i].buffer.front()); runs[i].buffer.pop();}
  74.                 runs[i].file.close();
  75.         }
  76.         printf("%ld\n", count);
  77.         input.close();
  78.         output.close();
  79.         return 0;
  80. }