Odpaliłem specjalny program optymalizacyjny w postaci trzech piw i z własnym IO zszedłem do sumy 0.73s ze wszystkich zestawów. I chyba przypomniałem sobie dlaczego nie lubię tych algorytmicznych zadań.
#include <cstdio>
#include <cstring>
#define NUM_BUFFER_SIZE 7 // liczba 7-cyfrowa
#define BUFFER_SIZE 524288 + NUM_BUFFER_SIZE
void ProcessNumber(int buttonIdx);
int MyAtoi(char* buffer);
size_t counterCount;
int counters[1000000] = { 0 }, maxCounterValue = 0, latestOverrideValue = 0;
int main()
{
static char buffer[BUFFER_SIZE];
FILE *input = stdin, *output = stdout;
size_t operationCount;
fscanf(input, "%d %d\n", &counterCount, &operationCount);
char numberBuffer[NUM_BUFFER_SIZE];
int numBufIdx = 0;
while(!feof(input))
{
int bytesRead = fread(buffer, 1, BUFFER_SIZE - NUM_BUFFER_SIZE, input);
for(int i = 0; i < bytesRead; i++)
{
if(i == BUFFER_SIZE && buffer[i] != ' ')
continue;
if(buffer[i] != ' ')
{
numberBuffer[numBufIdx] = buffer[i];
numBufIdx++;
}
if(buffer[i] == ' ' || (i == bytesRead - 1 && feof(input)))
{
numberBuffer[numBufIdx] = '\0';
numBufIdx = 0;
int number = MyAtoi(numberBuffer);
ProcessNumber(number);
}
}
if(numBufIdx != 0 && feof(input))
{
numberBuffer[numBufIdx] = '\0';
int number = MyAtoi(numberBuffer);
ProcessNumber(number);
}
}
int bufferIdx = 0;
numBufIdx = 0;
for(int counterIdx = 0; counterIdx < counterCount; counterIdx++)
{
int number = counters[counterIdx];
if(number < latestOverrideValue) number = latestOverrideValue;
int j = 30;
for(; number && j; --j, number /= 10)
numberBuffer[NUM_BUFFER_SIZE - 2 - 30 + j] = number % 10 + '0';
numberBuffer[NUM_BUFFER_SIZE - 1] = ' ';
size_t numberBufStart = NUM_BUFFER_SIZE - (30 - j) - 1, numberBufLength = 30 - j + 1;
memcpy(buffer + bufferIdx, numberBuffer + numberBufStart, numberBufLength);
bufferIdx += numberBufLength;
if(bufferIdx >= BUFFER_SIZE - NUM_BUFFER_SIZE)
{
fwrite(buffer, 1, bufferIdx, output);
bufferIdx = 0;
}
}
if(bufferIdx != 0)
fwrite(buffer, 1, bufferIdx, output);
return 0;
}
inline void ProcessNumber(int buttonIdx)
{
if(buttonIdx == counterCount + 1)
latestOverrideValue = maxCounterValue;
else
{
int counterValue = counters[buttonIdx - 1];
if(latestOverrideValue > counterValue)
counters[buttonIdx - 1] = latestOverrideValue + 1;
else
counters[buttonIdx - 1]++;
if(counters[buttonIdx - 1] > maxCounterValue)
maxCounterValue = counters[buttonIdx - 1];
}
}
inline int MyAtoi(char* buffer)
{
int number = 0;
for(int i = 0; buffer[i] != '\0' && buffer[i] != '\n'; i++)
{
number *= 10;
number += buffer[i] - '0';
}
return number;
}