Cod sursa(job #3240316)

Utilizator mircea_007Mircea Rebengiuc mircea_007 Data 14 august 2024 00:57:42
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
// solutie de taran, daca nu intra ma mai gandesc

#include <stdio.h>
#include <vector>

using ll = long long;

const int MAXN = 1e6;

struct Upd {
  int val;
  int time;

  Upd( int val = 0, int time = -1 ): val(val), time(time) {}
};

Upd aint[2 * (1 << 20)];
int aintn;

int main() {
  FILE *fin = fopen( "curcubeu.in", "r" );
  FILE *fout = fopen( "curcubeu.out", "w" );
  
  int n, a, b, c;
  fscanf( fin, "%d%d%d%d", &n, &a, &b, &c );

  aintn = 1;
  while( aintn < n )
    aintn <<= 1;

  for( int iter = 1; iter <= n; iter++ ){
    a = (a * (ll)iter) % n;
    b = (b * (ll)iter) % n;
    c = (c * (ll)iter) % n;

    int st = a < b ? a : b;
    int dr = a + b - st;

    st--;
    dr--;

    Upd rez( c, iter );

    { // cod de aint
      st += aintn - 1;
      dr += aintn - 1;

      while( st < dr ){
        if( !(st & 1) )
          aint[st++] = rez;
        if( dr & 1 )
          aint[dr--] = rez;

        st = (st - 1) >> 1;
        dr = (dr - 1) >> 1;
      }

      if( st == dr )
        aint[st] = rez;
    } // cod de aint
  }

  for( int i = 0; i < aintn - 1; i++ ){
    if( aint[i].time > aint[i * 2 + 1].time )
      aint[i * 2 + 1] = aint[i];

    if( aint[i].time > aint[i * 2 + 2].time )
      aint[i * 2 + 2] = aint[i];
  }

  for( int i = 0; i < n - 1; i++ )
    fprintf( fout, "%d\n", aint[aintn - 1 + i].val );

  fclose( fin );
  fclose( fout );
  return 0;
}