Cod sursa(job #2648513)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 11 septembrie 2020 12:01:16
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1000000 + 7;
int n;
int a;
int b;
int c;
int l[N];
int r[N];
int x[N];
int last[N];
int col[N];


char outBuffer[0x61A80]; unsigned int p;

__attribute__((always_inline)) void write(unsigned int x)
{
    unsigned int digits = x > 0x3B9AC9FF ? 0xA :
                 x > 0x5F5E0FF  ? 0x9 :
                 x > 0x98967F   ? 0x8 :
                 x > 0xF423F    ? 0x7 :
                 x > 0x1869F    ? 0x6 :
                 x > 0x270F     ? 0x5 :
                 x > 0x3E7      ? 0x4 :
                 x > 0x63       ? 0x3 :
                 x > 0x9        ? 0x2 : 0x1;

    for(unsigned int i = ~-digits; ~i; --i)
    {
        outBuffer[p + i] = x % 0xA + 0x30;

        x = x / 0xA;
    }

    p = p + digits;
    outBuffer[p++] = '\n';
    if (p > 400000 - 100)
    {
        puts(outBuffer);
    }
}

int main()
{
    freopen ("curcubeu.in", "r", stdin);
    freopen ("curcubeu.out", "w", stdout);

    scanf("%d %d %d %d", &n, &a, &b, &c);
    l[1] = min(a, b);
    r[1] = max(a, b);
    x[1] = c;
    last[1] = 1;
    for (int i = 2; i < n; i++)
    {
        a = 1LL * a * i % n;
        b = 1LL * b * i % n;
        c = 1LL * c * i % n;
        l[i] = min(a, b);
        r[i] = max(a, b);
        x[i] = c;
        last[i] = i;
    }
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = l[i]; j <= r[i]; j++)
        {
            if (col[j])
            {
                int u = last[j];
                last[j] = max(last[j], r[i]);
                j = u;
            }
            else
            {
                col[j] = x[i];
                last[j] = r[i];
            }
        }
    }
    for (int i = 1; i < n; i++)
    {
        write(col[i]);
    }
    puts(outBuffer);
}