Cod sursa(job #3240313)

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

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

using ll = long long;

const int MAXN = 1e6;

std::vector<int> aint[2 * (1 << 20)];
int aintn;

int rez[2 * (1 << 20)];

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--;

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

      while( st < dr ){
        if( !(st & 1) )
          aint[st++].push_back( c );
        if( dr & 1 )
          aint[dr--].push_back( c );

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

      if( st == dr )
        aint[st].push_back( c );
    } // cod de aint
  }

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

    if( i < aintn - 1 ){
      rez[i * 2 + 1] = rez[i];
      rez[i * 2 + 2] = rez[i];
    }
  }

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

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