Cod sursa(job #2447179)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 12 august 2019 12:37:53
Problema Secventa Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define OFFSET 30000
#define MAXINT 30000
#define NMAX 500010
#define MININT -30010
using namespace std;

vector<int> pos[60002];
int n, k;
int x;
int repr[NMAX];
int len[NMAX];
char fileText[5000000];

int chainJoin(int i)
{
  if (repr[i] == i)
    return i;
  repr[i] = chainJoin(repr[i]);
  return repr[i];
}

int merge(int i)
{
  if (repr[i - 1])
  {
    repr[i] = chainJoin(i - 1);
    len[repr[i]] += 1;
  }
  else
  {
    repr[i] = i;
    len[i] = 1;
  }
  if (repr[i + 1])
  {
    repr[i + 1] = repr[i];
    len[repr[i]] += len[i + 1];
  }
  return (len[repr[i]] >= k);
}

void read()
{
  FILE* file = fopen("secventa.in", "r");
  fgets(fileText, 5000000, file);

  int i = 0;
  while (fileText[i] != ' ')
    n = n * 10 + (fileText[i++] - '0');
  ++i;

  while (fileText[i] != '\n')
    k = k * 10 + (fileText[i++] - '0');
  

  fgets(fileText, 5000000, file);

  fclose(file);
  i = 0;
  int currentPos = 1;

  int sign = 1;
  int x = 0;
  while (fileText[i] != 0)
  {
    switch (fileText[i])
    {
    case '-':
      sign = -1;
      break;
    case ' ':
      pos[sign * x + OFFSET].push_back(currentPos++);
      sign = 1;
      x = 0;
      break;
    default:
      x = x * 10 + (fileText[i] - '0');
    }
    ++i;
  }
  pos[sign * x + OFFSET].push_back(currentPos++);
}

int main()
{
  freopen("secventa.out", "w", stdout);

  read();

  for (int maxSupport = MAXINT + OFFSET; maxSupport >= 0; --maxSupport)
  {
    for (int i = 0; i < pos[maxSupport].size(); ++i)
    {
      int currentPos = pos[maxSupport][i];
      if (merge(currentPos))
      {
        printf("%d %d %d", repr[currentPos], repr[currentPos] + k - 1, maxSupport - OFFSET);
        return 0;
      }
    }
  }

  return 0;
}