Cod sursa(job #2492404)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 14 noiembrie 2019 18:08:00
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <bits/stdc++.h>

#define NMAX 1000005
using namespace std;

class OutParser {

	private:

		static const int buffSZ = (1 << 15);
		ofstream File;
		char buff[buffSZ];
		int buffPos;
		vector <int> digits;

		void _advance() {

			if (++buffPos == buffSZ) {

				File.write(buff, buffSZ);
				buffPos = 0;
			}
		}

		void printChar(char no) {

			buff[buffPos] = no;
			_advance();
		}

	public:

		OutParser(const char *FileName) {

			File.open(FileName);
			digits.resize(11);
			buffPos = 0;
		}

		~OutParser() {

			File.write(buff, buffPos);
			buffPos = 0;
		}

		OutParser& operator <<(char ch) {

			printChar(ch);
			return *this;
		}

		OutParser& operator <<(int no) {

			int idx = 0;

			if (no == 0)
				digits[++idx] = 0;

			while (no) {

				digits[++idx] = no % 10;
				no /= 10;
			}

			for (; idx; --idx)
				printChar(digits[idx] + '0');

			return *this;
		}
};


ifstream fin("curcubeu.in");
OutParser fout("curcubeu.out");

struct chestie{
    int st, dr, c;
}query[NMAX];

int nex[NMAX], rez[NMAX];

int main()
{

    long long N, A1, B1, C1;
    fin >> N >> A1 >> B1 >> C1;

    query[1] = {.st = min(A1, B1), .dr = max(A1, B1), .c = C1};
    for(int i = 2; i <= N - 1; ++i){
        A1 = (A1 * i) % N;
        B1 = (B1 * i) % N;
        C1 = (C1 * i) % N;

        query[i] = {.st = min(A1, B1), .dr = max(A1, B1), .c = C1};
    }

    for(int i = 1; i < N; ++i)
        nex[i] = i + 1;

    int cnt = 0;
    for(int i = N - 1; i >= 1; --i){
        int j = query[i].st;
        while(j <= query[i].dr){
            if(rez[j] == 0)
                rez[j] = query[i].c, ++cnt;
            int cj = j;
            j = nex[j];

            nex[cj] = max(nex[cj], nex[query[i].dr]);
        }
        if(cnt == N - 1)
            break;
    }

    for(int i = 1; i < N; ++i)
        fout << rez[i] << '\n';
    return 0;
}