oj.uz

Submission #494104

# Submission time Handle Problem Language Result Execution time Memory
494104 2021-12-14T11:03:50 Z mircea_007 Restore Array (RMI19_restore) C++17
13 / 100
 389 ms 716 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 712 KB Output is correct
2 Correct 327 ms 580 KB Output is correct
3 Correct 323 ms 588 KB Output is correct
4 Correct 341 ms 588 KB Output is correct
5 Correct 367 ms 596 KB Output is correct
6 Correct 341 ms 588 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 712 KB Output is correct
2 Correct 327 ms 580 KB Output is correct
3 Correct 323 ms 588 KB Output is correct
4 Correct 341 ms 588 KB Output is correct
5 Correct 367 ms 596 KB Output is correct
6 Correct 341 ms 588 KB Output is correct
7 Correct 386 ms 608 KB Output is correct
8 Correct 382 ms 608 KB Output is correct
9 Correct 389 ms 608 KB Output is correct
10 Correct 358 ms 596 KB Output is correct
11 Correct 356 ms 588 KB Output is correct
12 Correct 370 ms 604 KB Output is correct
13 Correct 352 ms 608 KB Output is correct
14 Incorrect 383 ms 716 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -