Connection Status:
Competition Arena > Restrictions

Restrictions

SRM 762 · 2019-07-01 · by teja349

SRM 762 · 2019-07-01 · by teja349 · Simulation
Class Name: Restrictions
Return Type: int[]
Method Name: exist
Arg Types: (int, int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

You are given the task to construct an array of positive integers. The array A must have exactly n elements. You are given m additional constraints the array has to satisfy. Each constraint is of one of two kinds:

  1. If type[i] = 1: for each j such that l[i] <= j <= r[i], A[j] must be greater than or equal to val[i].
  2. If type[i] = 2: for each j such that l[i] <= j <= r[i], A[j] must be less than or equal to val[i].

Construct and return the array A. If no array matches all the given constraints, return the array {-1}. If multiple arrays match all the given constraints, return the lexicographically smallest of them.

Notes

  • Given two distinct arrays with the same number of elements, the lexicographically smaller one is the one that has a smaller value at the first index at which they differ.

Constraints

  • n will be between 1 and 500 inclusive.
  • m will be between 0 and 150 inclusive.
  • Each of the arrays type, l, r, and val will have exactly m elements.
  • Each element of type will be either 1 or 2.
  • For each valid i the inequalities 0 <= l[i] <= r[i] <= n-1 will hold.
  • Each element of val will be between 1 and 10^6 inclusive.
Examples
0)
407
5
{2,2,1,2,1}
{235,29,180,342,370}
{387,224,184,356,394}
{649034,421249,163850,833217,202538}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 163850, 163850, 163850, 163850, 163850, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 202538, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
1)
459
3
{1,1,1}
{231,67,414}
{280,188,455}
{282794,518378,999553}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 518378, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 282794, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 999553, 1, 1, 1 }
2)
454
5
{2,2,2,1,2}
{40,329,234,171,86}
{205,404,386,198,342}
{326506,927114,450730,269034,982730}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 269034, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
3)
432
3
{2,1,2}
{240,80,144}
{377,409,377}
{876353,847306,250625}
Returns: {-1 }
4)
427
4
{2,1,1,1}
{295,75,113,120}
{359,363,207,311}
{945258,909770,12033,930410}
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 930410, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 909770, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
57)
6
5
{1,1,2,2,2}
{0,1,2,1,2}
{5,3,3,4,2}
{10,18,25,26,16}
Returns: {-1 }

From condition 1 (0-based index) we can deduce that A[2] must be 18 or more. From condition 4 we can deduce that A[2] must be at most 16. This is a contradiction, there is no array that would have both properties at the same time.

58)
2
3
{1,2,2}
{0,1,0}
{1,1,0}
{3,4,4}
Returns: {3, 3 }

The arrays {3,3}, {3,4}, {4,3}, and {4,4} are the only four arrays that satisfy all the constraints. Among them, {3,3} is lexicographically smallest.

Submissions are judged against all 77 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Restrictions with a public method vector<int> exist(int n, int m, vector<int> type, vector<int> l, vector<int> r, vector<int> val) · 77 test cases · 2 s / 256 MB per case

Submitting as anonymous