제출 #494104

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494104		mircea_007	Restore Array (RMI19_restore)	C++17	13 / 100	389 ms	716 KiB

restore

// This program was written on 14.12.2021
// for problem restore from RMI 2019
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

// debug and local testing boilerplate

#ifdef LOCAL
#define DEBUG(var) printf("(!) DEBUG: "#var" = %d\n", var)
#define BREAKPOINT printf("(*) press enter\n");fgetc(stdin)
#else
#define DEBUG(var)
#define BREAKPOINT
#endif

#define MAXM 10000
#define MAXN  5000

#define LOWERBOUND 1
#define UPPERBOUND 0

int start[MAXM], end[MAXM];
int val[MAXM], type[MAXM];
int fill[MAXM];

int v[MAXN];

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch, semn = 1;

  while( isspace(ch = fgetc(fin)) );
  if( ch == '-' ){
    semn = -1;
    ch = fgetc(fin);
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n * semn;
}

int main(){
#ifdef LOCAL
  fin  = fopen("restore.in",  "r");
  fout = fopen("restore.out", "w");
#else
  fin = stdin;
  fout = stdout;
#endif

  int n, m, i, j, dont_add, should_add, bad;
  
  n = fgetint();
  m = fgetint();
  
  for( i = 0 ; i < m ; i++ ){
    start[i] = fgetint();
    end[i]   = fgetint();
    val[i]   = end[i] - start[i] + 1 - fgetint() + 1;
    type[i]  = fgetint();
    fill[i] = 0;
  }
  
  for( i = 0 ; i < n ; i++ ){
    dont_add = should_add = 0;
    for( j = 0 ; j < m ; j++ ){// O(M * N) is fast enough
      if( start[j] <= i && i <= end[j] ){
        if( type[j] == UPPERBOUND ){
          dont_add |= (fill[j] + 1 == val[j]);
        }else{
          dont_add |= (start[j] + fill[j] - 1 == end[j]);// the interval is full
          should_add |= (fill[j] < val[j]);// we have an interval to fill
        }
      }
    }
    
    DEBUG(dont_add);
    DEBUG(should_add);
    v[i] = !dont_add && should_add;
    DEBUG(v[i]);

    for( j = 0 ; j < m ; j++ )// update fills
      if( start[j] <= i && i <= end[j] )
        fill[j] += v[i];
    
    BREAKPOINT;
  }
  
  // check if everything is valid
  bad = 0;
  for( i = 0 ; i < m ; i++ ){
    if( type[i] == UPPERBOUND )
      bad |= (fill[i] >= val[i]);
    else
      bad |= (fill[i] < val[i]);
  }
  
  if( bad )
    fprintf(fout, "-1");
  else{
    for( i = 0 ; i < n ; i++ ){
      fputc(v[i] + '0', fout);
      fputc(' ', fout);
    }
  }
  fputc('\n', fout);
  
  fclose(fin);
  fclose(fout);
  return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55