Codeforces Round #481 (Div.3)

CodeForces Contest: https://codeforces.com/contest/978
Probelm Set PDF: https://file.beiyanpiki.cn/ACM/Codeforces%20Round%20%23481%20%28Div.%203%29
官方英文题解: https://codeforces.com/blog/entry/59430

A. Remove Duplicates

Petya has an array $a$ consisting of $n$ integers. He wants to remove duplicate (equal) elements.

Petya wants to leave only the rightmost entry (occurrence) for each element of the array. The relative order of the remaining unique elements should not be changed.

input

The first line contains a single integer $n$ ( $1 \le n \le 50$ ) — the number of elements in Petya's array.

The following line contains a sequence $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 1\,000$ ) — the Petya's array.

output

In the first line print integer $x$ — the number of elements which will be left in Petya's array after he removed the duplicates.

In the second line print $x$ integers separated with a space — Petya's array after he removed the duplicates. For each unique element only the rightmost entry should be left.

Examples

case 1:

input	output
6<br>1 5 5 1 6 1	3<br>5 6 1

case 2:

input	output
5<br>2 4 2 4 4	2<br>2 4

case 3:

input	output
5<br>6 6 6 6 6	1<br>6

Note

In the first example you should remove two integers $1$ , which are in the positions $1$ and $4$ . Also you should remove the integer $5$ , which is in the position $2$ .

In the second example you should remove integer $2$ , which is in the position $1$ , and two integers $4$ , which are in the positions $2$ and $4$ .

In the third example you should remove four integers $6$ , which are in the positions $1$ , $2$ , $3$ and $4$ .

Solve

这是一道800分的签到题。
官方标签：implementation

第一行给出一个数列长度n
第二行给出长度为n的数列 $a$

第一行输出一共出现了几个数字
第二行按最后一次出现的顺序输出这几个数字

从左到右遍历，用map储存数字是否已经出现。

#include <bits/stdc++.h>
using namespace std;

int main() {

    int a[100000];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    map<int, int> mp;
    vector<int> res;
    for (int i = n - 1; i >= 0; i--) {
        if (!mp[a[i]]++)
            res.push_back(a[i]);
    }
    bool flag = false;
    cout << res.size() << endl;
    for (int i = res.size() - 1; i >= 0; i--) {
        if (flag)
            cout << " ";
        cout << res[i];
        flag = true;
    }

    return 0;
}

B. File Name

You can not just take the file and send it. When Polycarp trying to send a file in the social network "Codehorses", he encountered an unexpected problem. If the name of the file contains three or more "x" (lowercase Latin letters "x") in a row, the system considers that the file content does not correspond to the social network topic. In this case, the file is not sent and an error message is displayed.

Determine the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. Print 0 if the file name does not initially contain a forbidden substring "xxx".

You can delete characters in arbitrary positions (not necessarily consecutive). If you delete a character, then the length of a string is reduced by $1$ . For example, if you delete the character in the position $2$ from the string "exxxii", then the resulting string is "exxii".

input

The first line contains integer $n$ $(3 \le n \le 100)$ — the length of the file name.

The second line contains a string of length $n$ consisting of lowercase Latin letters only — the file name.

output

Print the minimum number of characters to remove from the file name so after that the name does not contain "xxx" as a substring. If initially the file name dost not contain a forbidden substring "xxx", print 0.

Examples

case 1:

input	output
6<br>xxxiii	1

case 2:

input	output
5<br>xxoxx	0

case 3:

input	output
10<br>xxxxxxxxxx	8

Note

In the first example Polycarp tried to send a file with name contains number $33$ , written in Roman numerals. But he can not just send the file, because it name contains three letters "x" in a row. To send the file he needs to remove any one of this letters.

Solve

这是一道700分的签到题。
官方标签：greedy string
第一行给出字符串的长度n
第二行给出长度为n的字符串s

问该字符串包含多少个子字符串"xxx"

从左向右遍历，使用string的substr函数即可

#include <bits/stdc++.h>
using namespace std;

int main() {
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);

    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    for (int i = 0; i < n - 2; i++) {
        if (s.substr(i, 3) == "xxx")
            cnt++;
    }
    cout << cnt << endl;

    return 0;
}

C. Letters

There are $n$ dormitories in Berland State University, they are numbered with integers from $1$ to $n$ . Each dormitory consists of rooms, there are $a_i$ rooms in $i$ -th dormitory. The rooms in $i$ -th dormitory are numbered from $1$ to $a_i$ .

A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all $n$ dormitories is written on an envelope. In this case, assume that all the rooms are numbered from $1$ to $a_1 + a_2 + \dots + a_n$ and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.

For example, in case $n=2$ , $a_1=3$ and $a_2=5$ an envelope can have any integer from $1$ to $8$ written on it. If the number $7$ is written on an envelope, it means that the letter should be delivered to the room number $4$ of the second dormitory.

For each of $m$ letters by the room number among all $n$ dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.

input

The first line contains two integers $n$ and $m$ $(1 \le n, m \le 2 \cdot 10^{5})$ — the number of dormitories and the number of letters.

The second line contains a sequence $a_1, a_2, \dots, a_n$ $(1 \le a_i \le 10^{10})$ , where $a_i$ equals to the number of rooms in the $i$ -th dormitory. The third line contains a sequence $b_1, b_2, \dots, b_m$ $(1 \le b_j \le a_1 + a_2 + \dots + a_n)$ , where $b_j$ equals to the room number (among all rooms of all dormitories) for the $j$ -th letter. All $b_j$ are given in increasing order.

output

Print $m$ lines. For each letter print two integers $f$ and $k$ — the dormitory number $f$ $(1 \le f \le n)$ and the room number $k$ in this dormitory $(1 \le k \le a_f)$ to deliver the letter.

Examples

case 1:

input	output
3 6<br>10 15 12<br>1 9 12 23 26 37	1 1<br>1 9<br>2 2<br>2 13<br>3 1<br>3 12

case 2:

input	output
2 3<br>5 10000000000<br>5 6 9999999999	1 5<br>2 1<br>2 9999999994

Note

In the first example letters should be delivered in the following order:

the first letter in room $1$ of the first dormitory
the second letter in room $9$ of the first dormitory
the third letter in room $2$ of the second dormitory
the fourth letter in room $13$ of the second dormitory
the fifth letter in room $1$ of the third dormitory
the sixth letter in room $12$ of the third dormitory

Solve

这是一道1000分的搜索题。
官方标签：binary search implementation two pointers

题目在第一行给出两个整数n，m，分别表示宿舍楼的个数和待测数据的个数
接下来一行输入长度为n的数组 $a$ ，表示每个宿舍楼的房间个数
接下来一行输入m个查询数据。

房间的编号按宿舍楼的顺序。从1开始计数，标记第一幢楼到最后一间房间；接下来紧接着之前的计数标记第二幢楼的第一间房间至最后一间，以此类推。

现在，邮递员需要递送一封标有房间号的信送往宿舍楼的一个房间。对于每个查询数据 $b[ i ]$ ，你需要查询这封信应该被送往哪个宿舍楼的哪个房间。

题目中给予的是每个宿舍楼的房间数，我们先要把他转化成每幢楼起始的标号。
接下来使用二分查找，找出应该送往哪一个宿舍楼 $t$ ，而房间则是 $b[ i ] - a[ t ]$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);

    int n, k;
    ll p[200000 + 50];
    ll sum = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        sum += p[i];
        p[i] = sum;
    }

    // for (int i = 0; i < n; i++) {
    //     cout << p[i] << endl;
    // }
    // cout << "===" << endl;
    while (k--) {
        ll t;
        cin >> t;
        int res = lower_bound(p, p + n, t) - p;
        cout << res + 1 << " ";
        if (res == 0)
            cout << t << endl;
        else
            cout << t - p[res - 1] << endl;
    }

    return 0;
}

D. Almost Arithmetic Progression

Polycarp likes arithmetic progressions. A sequence $[a_1, a_2, \dots, a_n]$ is called an arithmetic progression if for each $i$ ( $1 \le i < n$ ) the value $a_{i+1} - a_i$ is the same. For example, the sequences $[42]$ , $[5, 5, 5]$ , $[2, 11, 20, 29]$ and $[3, 2, 1, 0]$ are arithmetic progressions, but $[1, 0, 1]$ , $[1, 3, 9]$ and $[2, 3, 1]$ are not.

It follows from the definition that any sequence of length one or two is an arithmetic progression.

Polycarp found some sequence of positive integers $[b_1, b_2, \dots, b_n]$ . He agrees to change each element by at most one. In the other words, for each element there are exactly three options: an element can be decreased by $1$ , an element can be increased by $1$ , an element can be left unchanged.

Determine a minimum possible number of elements in $b$ which can be changed (by exactly one), so that the sequence $b$ becomes an arithmetic progression, or report that it is impossible.

It is possible that the resulting sequence contains element equals $0$ .

input

The first line contains a single integer $n$ $(1 \le n \le 100\,000)$ — the number of elements in $b$ .

The second line contains a sequence $b_1, b_2, \dots, b_n$ $(1 \le b_i \le 10^{9})$ .

output

If it is impossible to make an arithmetic progression with described operations, print -1. In the other case, print non-negative integer — the minimum number of elements to change to make the given sequence becomes an arithmetic progression. The only allowed operation is to add/to subtract one from an element (can't use operation twice to the same position).

Examples

case 1:

input	output
4<br>24 21 14 10	3

case 2:

input	output
2<br>500 500	0

case 3:

input	output
3<br>14 5 1	-1

case 4:

input	output
5<br>1 3 6 9 12	1
### Note
In the first example Polycarp should increase the first number on $1$ , decrease the second number on $1$ , increase the third number on $1$ , and the fourth number should left unchanged. So, after Polycarp changed three elements by one, his sequence became equals to $[25, 20, 15, 10]$ , which is an arithmetic progression.

In the second example Polycarp should not change anything, because his sequence is an arithmetic progression.

In the third example it is impossible to make an arithmetic progression.

In the fourth example Polycarp should change only the first element, he should decrease it on one. After that his sequence will looks like $[0, 3, 6, 9, 12]$ , which is an arithmetic progression.

Solve

这是一道1500分的思维题。
官方标签： brute force implementation math

第一行给一个数组长度n
第二行给出一个长度为n的数列 $a$

问该数列能否让数列中的各个元素+1或-1或不变, 使该数列变成一个差为整数的等差数列。如果可以，则输出变成等差数列的最小操作数，否则输出-1。

首先，要变成差为整数的等差数列，只需要判断

$a[ 0 ] - a[ n - 1 ]$
$a[ 0 ] - ( a[ n - 1 ] + 1 )$
$a[ 0 ] - ( a[ n - 1 ] - 1 )$
$( a[ 0 ] - 1 ) - ( a[ n - 1 ] - 1 )$
$( a[ 0 ] - 1 ) - a[ n - 1 ]$
$( a[ 0 ] - 1 ) - ( a[ n - 1 ] + 1 )$
$( a[ 0 ] + 1 ) - ( a[ n - 1 ] - 1 )$
$( a[ 0 ] + 1 ) - a[ n - 1 ]$
$( a[ 0 ] + 1 ) - ( a[ n - 1 ] + 1 )$

的公差是否为整数。

对于每种可能性，公差是否为整数，是的话继续接下来的操作，否则输出继续判断下一种可能.
如果公差是整数，则将该数列从前向后遍历，判断 $| a[ 0 ] + i * d - a[ i ] | \le 1$ 是否成立，如果数列所有元素全都满足，则得到步数。

经过8次暴力计算后，得出最小步数。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll ss[100000 + 50];

const int inf = 0x3f3f3f3f;
int n;
int go(int a, int b) {
    ll aa = ss[n - 1] + a;
    ll bb = ss[0] + b;
    ll def = aa - bb;

    if (def % (n - 1) != 0)
        return inf;
    ll d = def / (n - 1);
    ll now = bb;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        // cout << now << " " << ss[i] << endl;
        if (fabs(now - ss[i]) <= 1) {
            if (now - ss[i] != 0)
                cnt++;
            now += d;
            continue;
        } else {
            return inf;
        }
    }
    now = ss[0];
    // cout << cnt << endl;
    return cnt;
}

int main() {
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> ss[i];
    }
    if (n == 1) {
        cout << "0" << endl;
        return 0;
    }
    int res = inf;
    res = min(res, (go(0, 0)));
    res = min(res, (go(0, 1)));
    res = min(res, (go(0, -1)));
    res = min(res, (go(-1, -1)));
    res = min(res, (go(-1, 0)));
    res = min(res, (go(-1, 1)));
    res = min(res, (go(1, -1)));
    res = min(res, (go(1, 0)));
    res = min(res, (go(1, 1)));
    if (res == inf)
        cout << "-1" << endl;
    else
        cout << res << endl;

    return 0;
}

E. Bus Video System

The busses in Berland are equipped with a video surveillance system. The system records information about changes in the number of passengers in a bus after stops.

If $x$ is the number of passengers in a bus just before the current bus stop and $y$ is the number of passengers in the bus just after current bus stop, the system records the number $y-x$ . So the system records show how number of passengers changed.

The test run was made for single bus and $n$ bus stops. Thus, the system recorded the sequence of integers $a_1, a_2, \dots, a_n$ (exactly one number for each bus stop), where $a_i$ is the record for the bus stop $i$ . The bus stops are numbered from $1$ to $n$ in chronological order.

Determine the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to $w$ (that is, at any time in the bus there should be from $0$ to $w$ passengers inclusive).

input

The first line contains two integers $n$ and $w$ $(1 \le n \le 1\,000, 1 \le w \le 10^{9})$ — the number of bus stops and the capacity of the bus.

The second line contains a sequence $a_1, a_2, \dots, a_n$ $(-10^{6} \le a_i \le 10^{6})$ , where $a_i$ equals to the number, which has been recorded by the video system after the $i$ -th bus stop.

output

Print the number of possible ways how many people could be in the bus before the first bus stop, if the bus has a capacity equals to $w$ . If the situation is contradictory (i.e. for any initial number of passengers there will be a contradiction), print 0.

Examples

case 1:

input	output
3 5<br>2 1 -3	3

case 2:

input	output
2 4<br>-1 1	4

case 3:

input	output
4 10<br>2 4 1 2	2

Note

In the first example initially in the bus could be $0$ , $1$ or $2$ passengers.

In the second example initially in the bus could be $1$ , $2$ , $3$ or $4$ passengers.

In the third example initially in the bus could be $0$ or $1$ passenger.

Solve

这是一道1400分的数学题。
官方标签： math

第一行给出车站的个数n和公交车的最大载客量w
第二行给出每个车站上下车的人数

问在起始站（第一个车站不是起始站），公交车的人数有多少种可能性。

根据常识（真的是常识），公交车里面的乘客数量不可能为负数（废话），同时也不能超载（遵守交通规则）。
首先我们假设公交车上有 $x$ 人，我们从第一个车站开始计算，计算当前车站比起起始车站，多或少了多少个人。我们需要记录最多多了多少个人 $maxw$ ，最少少了多少个人 $minw$ ，最后的种数 $T = w - maxw + minw + 1$ 。
当然 $T < 0$ 就输出0了

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    int n;
    ll w;
    cin >> n >> w;
    ll now = 0, maxw = 0, minw = 0;
    for (int i = 0; i < n; i++) {
        ll t;
        cin >> t;
        now += t;
        maxw = max(maxw, now);
        minw = min(minw, now);
    }

    int res = w - maxw + minw + 1;
    if (res < 0)
        cout << "0" << endl;
    else
        cout << res << endl;

    return 0;
}

F. Mentors

In BerSoft $n$ programmers work, the programmer $i$ is characterized by a skill $r_i$ .

A programmer $a$ can be a mentor of a programmer $b$ if and only if the skill of the programmer $a$ is strictly greater than the skill of the programmer $b$ $(r_a > r_b)$ and programmers $a$ and $b$ are not in a quarrel.

You are given the skills of each programmers and a list of $k$ pairs of the programmers, which are in a quarrel (pairs are unordered). For each programmer $i$ , find the number of programmers, for which the programmer $i$ can be a mentor.

input

The first line contains two integers $n$ and $k$ $(2 \le n \le 2 \cdot 10^5$ , $0 \le k \le \min(2 \cdot 10^5, \frac{n \cdot (n - 1)}{2}))$ — total number of programmers and number of pairs of programmers which are in a quarrel.

The second line contains a sequence of integers $r_1, r_2, \dots, r_n$ $(1 \le r_i \le 10^{9})$ , where $r_i$ equals to the skill of the $i$ -th programmer.

Each of the following $k$ lines contains two distinct integers $x$ , $y$ $(1 \le x, y \le n$ , $x \ne y)$ — pair of programmers in a quarrel. The pairs are unordered, it means that if $x$ is in a quarrel with $y$ then $y$ is in a quarrel with $x$ . Guaranteed, that for each pair $(x, y)$ there are no other pairs $(x, y)$ and $(y, x)$ in the input.

output

Print $n$ integers, the $i$ -th number should be equal to the number of programmers, for which the $i$ -th programmer can be a mentor. Programmers are numbered in the same order that their skills are given in the input.

Examples

case 1:

input	output
4 2<br>10 4 10 15<br>1 2<br>4 3	0 0 1 2

case 2:

input	output
10 4<br>5 4 1 5 4 3 7 1 2 5<br>4 6<br>2 1<br>10 8<br>3 5	5 4 0 5 3 3 9 0 2 5

Note

In the first example, the first programmer can not be mentor of any other (because only the second programmer has a skill, lower than first programmer skill, but they are in a quarrel). The second programmer can not be mentor of any other programmer, because his skill is minimal among others. The third programmer can be a mentor of the second programmer. The fourth programmer can be a mentor of the first and of the second programmers. He can not be a mentor of the third programmer, because they are in a quarrel.

Solve

这是一道1500分的题。
官方标签： binary search data structures implementation

第一行给出两个数，人数 $n$ , 仇人对数 $k$
第二行给出长度为n的数列 $a$ ， $a[ i ]$ 表示第i个人的能力值
接下来 $k$ 行给出仇人编号i j

题目给出定义：

能力值高的人能成为能力值低的人的师傅
互为仇人无法达成师徒关系

求出每个人最多能有几个徒弟

首先我们从k对仇人中，将能力值低的人的编号 $i$ 存入能力值高的仇人列表（毕竟能力值低的连人成为师傅的资本都没有）
然后我们复制数列 $a$ 为 $b$ ,并对 $b$ 从小到大进行排序.

接着我们计算每个人的土地个数，lower_bound二分查找第 $i$ 个人在数列 $b$ 中位于第 $pos$ 个位置，有pos个人能成为他的徒弟，再将这pos个人中找到是不是有仇人，有仇人则去掉这个人，得到结果。

#include <bits/stdc++.h>
using namespace std;

int n, k;
int a[200000 + 50];
int b[200000 + 50];
vector<int> v[200000 + 50];
int main() {
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    for (int i = 0; i < k; i++) {
        int t1, t2;

        cin >> t1 >> t2;
        t1--;
        t2--;
        if (a[t1] < b[t2])
            swap(t1, t2);
        v[t1].push_back(t2);
    }
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
        int num = lower_bound(b, b + n, a[i]) - b;
        for (int j = 0; j < v[i].size(); j++) {
            if (a[v[i][j]] < a[i])
                num--;
        }
        cout << num << " ";
    }
    return 0;
}

G. Petya's Exams

Petya studies at university. The current academic year finishes with $n$ special days. Petya needs to pass $m$ exams in those special days. The special days in this problem are numbered from $1$ to $n$ .

There are three values about each exam:

$s_i$ — the day, when questions for the $i$ -th exam will be published,
$d_i$ — the day of the $i$ -th exam ( $s_i < d_i$ ),
$c_i$ — number of days Petya needs to prepare for the $i$ -th exam. For the $i$ -th exam Petya should prepare in days between $s_i$ and $d_i-1$ , inclusive.

There are three types of activities for Petya in each day: to spend a day doing nothing (taking a rest), to spend a day passing exactly one exam or to spend a day preparing for exactly one exam. So he can't pass/prepare for multiple exams in a day. He can't mix his activities in a day. If he is preparing for the $i$ -th exam in day $j$ , then $s_i \le j < d_i$ .

It is allowed to have breaks in a preparation to an exam and to alternate preparations for different exams in consecutive days. So preparation for an exam is not required to be done in consecutive days.

Find the schedule for Petya to prepare for all exams and pass them, or report that it is impossible.

input

The first line contains two integers $n$ and $m$ $(2 \le n \le 100, 1 \le m \le n)$ — the number of days and the number of exams.

Each of the following $m$ lines contains three integers $s_i$ , $d_i$ , $c_i$ $(1 \le s_i < d_i \le n, 1 \le c_i \le n)$ — the day, when questions for the $i$ -th exam will be given, the day of the $i$ -th exam, number of days Petya needs to prepare for the $i$ -th exam.

Guaranteed, that all the exams will be in different days. Questions for different exams can be given in the same day. It is possible that, in the day of some exam, the questions for other exams are given.

output

If Petya can not prepare and pass all the exams, print -1. In case of positive answer, print $n$ integers, where the $j$ -th number is:

$(m + 1)$ , if the $j$ -th day is a day of some exam (recall that in each day no more than one exam is conducted),
zero, if in the $j$ -th day Petya will have a rest,
$i$ ( $1 \le i \le m$ ), if Petya will prepare for the $i$ -th exam in the day $j$ (the total number of days Petya prepares for each exam should be strictly equal to the number of days needed to prepare for it).

Assume that the exams are numbered in order of appearing in the input, starting from $1$ .

If there are multiple schedules, print any of them.

Examples

case 1:

input	output
5 2<br>1 3 1<br>1 5 1	1 2 3 0 3

case 2:

input	output
3 2<br>1 3 1<br>1 2 1<br>	-1

case 3:

input	output
10 3<br>4 7 2<br>1 10 3<br>8 9 1	2 2 2 1 1 0 4 3 4 4

Note

In the first example Petya can, for example, prepare for exam $1$ in the first day, prepare for exam $2$ in the second day, pass exam $1$ in the third day, relax in the fourth day, and pass exam $2$ in the fifth day. So, he can prepare and pass all exams.

In the second example, there are three days and two exams. So, Petya can prepare in only one day (because in two other days he should pass exams). Then Petya can not prepare and pass all exams.

Solve

这是一道1800分的贪心题。
官方标签： greedy implementation sortings

第一行给出小明有n天时间，他需要进行T门开始
接下来T行，分别给出 $s_i$ , $d_i$ , $c_i$ $，表示每门开始的开始发表时间，考试时间，复习时间。

每门考试只有发表之后，小明才能开始复习；只有复习完之后，并且准时参加考试才能通过考试

现在问小明的作息时间。
如果小明无法顺利通过任何一门考试，则输出-1即可。
如果可以，则输出他每天的作息。

如果是考试日，输出 $n + 1$
如果是复习日，则输出当前复习的是 $k$ 考试
如果是休息日，则输出 $0$

这是个区间贪心题目

首先按考试开始的时间进行排序。
首先将作息安排数列 $res$ 全部设置为 $0$ （即全都休息）
然后安排序后的考试顺序，从布置日起到考试日，对日子标记上当前复习的科目，如果之前已经标记过，则跳过标记之后的日子；如果到了考试日还没标记完，则表示该科目还没复习完，输出-1跳出程序即可。最后将该门科目的考试的日字标记为考试 $n + 1$

这样让第1-k门科目进行相同的操作，最后输出 $res$ 数列即可。

//
// Created by beiyanpiki on 19-4-5.
//

#include <bits/stdc++.h>

using namespace std;

typedef struct {
    int s, d, c;
    int id;
} Test;

bool cmp(Test A, Test B) {
    return A.d < B.d;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);

    int d, n;
    Test t[105];


    cin >> d >> n;
    for (int i = 0; i < n; i++) {
        cin >> t[i].s >> t[i].d >> t[i].c;
        t[i].id = i + 1;
    }

    sort(t, t + n, cmp);
    bool flag = true;
    int res[105];
    memset(res, 0, sizeof(res));
    for (int i = 0; i < n; i++) {
        for (int j = t[i].s; j != t[i].d; j++) {
            if (j == t[i].d) {
                flag = false;
                break;
            }
            if (res[j])
                continue;
            if (t[i].c) {
                res[j] = t[i].id;
            }
            if (t[i].c > 0)
                t[i].c--;
        }
        if (t[i].c)flag = false;
        if (flag)
            res[t[i].d] = n + 1;
        else
            break;
    }
    if (!flag) {
        cout << "-1" << endl;
    } else {
        for (int i = 1; i <= d; i++) {
            if (i != 1)cout << " ";
            cout << res[i];
        }
        cout << endl;
    }

}