Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;

int n,upper[222],lower[222],c[222][222],l[222],r[222],seen[222];

void addMax(int x,int y,int v)
{
    for (int i=1;i<=n;i++)
    {
        if (i<x || i>y)
        {
            if (v>=1 && v<=n) c[i][v]=-1;
        }
        else
            if (upper[i]>=v) upper[i]=v;
    }
}

void addMin(int x,int y,int v)
{
    for (int i=1;i<=n;i++)
    {
        if (i<x || i>y)
        {
            if (v>=1 && v<=n) c[i][v]=-1;
        }
        else
            if (lower[i]<=v) lower[i]=v;
    }
}

int findMatch(int x)
{
    if (!x) return 1;
    if (seen[x]) return 0;
    seen[x]=1;
    for (int y=1;y<=n;y++)
        if (c[x][y]==1 && findMatch(l[y]))
        {
            r[x]=y; l[y]=x;
            return 1;
        }
    return 0;
}

int main()
{
    int m,t,x,y,v;
    cin >> n >> m;
    for (int i=1;i<=n;i++) upper[i]=n, lower[i]=1;

    while (m--)
    {
        scanf("%d%d%d%d",&t,&x,&y,&v);
        if (t==1) addMax(x,y,v);
        else addMin(x,y,v);
    }

    for (int i=1;i<=n;i++)
        for (int j=lower[i];j<=upper[i];j++)
            if (!c[i][j])   c[i][j]=1;

    int match=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++) seen[j]=0;
        match+=findMatch(i);
    }

    if (match<n) puts("-1");
    else
        for (int i=1;i<=n;i++) cout << r[i] << (i==n?'\n':' ');
}

Code mẫu của happyboy99x

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

const int N = 200;
pair<int, int> possiblePosition[N], possibleValue[N];
vector<int> g[N];
int n, m, my[N], vx[N];

void fasten(pair<int, int> &a, const pair<int, int> &b) {
    a.first = max(a.first, b.first);
    a.second = min(a.second, b.second);
}

void enter() {
    cin >> n >> m;
    fill_n(possiblePosition, n, pair<int, int>(0, n));
    fill_n(possibleValue, n, pair<int, int>(0, n));
    for(int i = 0; i < m; ++i) {
        int type, x, y, v; cin >> type >> x >> y >> v; --x; --v;
        if(type == 1) {
            fasten(possiblePosition[v], make_pair(x, y));
            for(int p = x; p < y; ++p)
                fasten(possibleValue[p], make_pair(0, v + 1));
        } else {
            fasten(possiblePosition[v], make_pair(x, y));
            for(int p = x; p < y; ++p)
                fasten(possibleValue[p], make_pair(v, n));
        }
    }
}

void buildGraph() {
    for(int num = 0; num < n; ++num)
        for(int pos = possiblePosition[num].first; pos < possiblePosition[num].second; ++pos)
            if(possibleValue[pos].first <= num && num < possibleValue[pos].second)
                g[num].push_back(pos);
}

bool dfs(int u) {
    if(u == -1) return true;
    if(vx[u]) return false;
    vx[u] = true;
    for(vector<int>::const_iterator v = g[u].begin(); v != g[u].end(); ++v)
        if(dfs(my[*v])) return my[*v] = u, true;
    return false;
}

int maxMatch() {
    int res = 0;
    memset(my, -1, sizeof my);
    for(int i = 0; i < n; ++i) {
        memset(vx, 0, sizeof vx);
        if(dfs(i)) ++res;
    }
    return res;
}

void solve() {
    if(maxMatch() == n) {
        for(int i = 0; i < n; ++i) cout << my[i] + 1 << ' ';
        cout << '\n';
    } else cout << -1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    buildGraph();
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(it = typeof((a).begin()); it != (a).end(); it++)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 202;
using namespace std;
int a[N][N], matchY[N], MIN[N], MAX[N], myList[N];
bool was[N], foundPath;
int n, m;

void dfs(int u) {
    REP(v, 1, n) if (a[u][v] && !was[v]) {
        was[v] = 1;
        if (matchY[v] == 0) foundPath = 1;
        else dfs(matchY[v]);
        if (foundPath) {
            matchY[v] = u;
            return;
        }
    }
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    REP(i, 1, n) REP(j, 1, n) a[i][j] = 1;
    int kind, x, y, v;
    FOR(i, 0, m) {
        cin >> kind >> x >> y >> v;
        FOR(i, 1, x) a[v][i] = 0;
        REP(i, y + 1, n) a[v][i] = 0;
        if (kind == 1) {
            REP(i, x, y) {
                if (MAX[i] && MAX[i] < v)
                    a[v][i] = 0;
                else MAX[i] = v;
            }
        }
        else {
            REP(i, x, y) {
                if (MIN[i] && MIN[i] > v)
                    a[v][i] = 0;
                else MIN[i] = v;
            }
        }
    }
    REP(i, 1, n) REP(j, 1, n) {
        int mi = MIN[j], ma = MAX[j];
        if (ma == 0) ma = n;
        if (i < mi || ma < i) a[i][j] = 0;
    }
    int nList = 0;
    REP(i, 1, n) myList[nList++] = i;
    bool stop;
    do {
        REP(i, 1, n) was[i] = 0;
        stop = 1;
        REPD(i, nList - 1, 0) {
            foundPath = 0;
            dfs(myList[i]);
            if (foundPath) {
                myList[i] = myList[--nList];
                stop = 0;
            }
        }
    } while (!stop);
    if (nList)
        cout << -1;
    else
        REP(i, 1, n) cout << matchY[i] << ' ';
    return 0;
}

Code mẫu của RR

#include <sstream>
#include <iomanip>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++)
#define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--)
#define SET(a,v) memset(a,v,sizeof(a))
#define sqr(x) ((x)*(x))
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair

#define DEBUG(x) cout << #x << " = "; cout << x << endl;
#define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl;
#define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl;
using namespace std;

//Buffer reading
int INP,AM,REACHEOF;
const int BUFSIZE = (1<<12) + 17;
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp && !REACHEOF) { \
        memset(BUF,0,sizeof BUF);\
        int inpzzz = fread(BUF,1,BUFSIZE,stdin);\
        if (inpzzz != BUFSIZE) REACHEOF = true;\
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

const long double PI = acos((long double) -1.0);
const int MN = 211;

int n, m;
int nn[MN], ln[MN];
bool seen[MN];
int mx[MN], my[MN];
pair<int,int> range[MN];

bool dfs(int x) {
    FOR(y,nn[x],ln[x])
    if (range[y].first <= x && x <= range[y].second) {
        if (seen[y]) continue;

        seen[y] = true;
        if (!my[y] || dfs(my[y])) {
            my[y] = x;
            mx[x] = y;
            return true;
        }
    }
    return false;
}

bool solve() {
    memset(mx, 0, sizeof mx);
    memset(my, 0, sizeof my);

    FOR(i,1,n) if (!mx[i]) {
        memset(seen, false, sizeof seen);
        dfs(i);
    }

    FOR(i,1,n) if (!mx[i]) return false;
    return true;
}

int main() {
    while (scanf("%d%d", &n, &m) == 2) {
        FOR(i,1,n) {
            nn[i] = 1, ln[i] = n;
            range[i] = make_pair(1, n);
        }

        bool ok = true;
        FOR(i,1,m) {
            int type, x, y, v; scanf("%d%d%d%d", &type, &x, &y, &v);
            if (type == 1) {
                FOR(u,x,y) ln[u] = min(ln[u], v);
            }
            else {
                FOR(u,x,y) nn[u] = max(nn[u], v);
            }

            if (range[v].second < x || range[v].first > y) ok = false;
            else {
                range[v].first = max(range[v].first, x);
                range[v].second = min(range[v].second, y);
            }
        }

        FOR(i,1,n) if (ln[i] < nn[i]) ok = false;

        if (!ok) {
            puts("-1");
            continue;
        }

        if (solve()) {
            FOR(i,1,n) printf("%d ", mx[i]);
            puts("");
        }
        else puts("-1");
    }
    return 0;
}

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef unsigned long long ull;

#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)
#define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
//#define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))

template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; }
template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T> T sqr(T x) { return x * x; }
template<class T> T cube(T x) { return x * x * x; }
template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); }

const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
    if (rsz <= 0) {
        ptr = 0;
        rsz = (int) fread(bf, 1, bfsz, stdin);
        if (rsz <= 0)
            return EOF;
    }
    --rsz;
    return bf[ptr++];
}
void ga(char &c) {
    c = EOF;
    while (!isalpha(c))
        c = gc();
}
int gs(char s[]) {
    int l = 0;
    char c = gc();
    while (isspace(c))
        c = gc();
    while (c != EOF && !isspace(c)) {
        s[l++] = c;
        c = gc();
    }
    s[l] = '\0';
    return l;
}
template<class T> bool gi(T &v) {
    v = 0;
    char c = gc();
    while (c != EOF && c != '-' && !isdigit(c))
        c = gc();
    if (c == EOF)
        return false;
    bool neg = c == '-';
    if (neg)
        c = gc();
    while (isdigit(c)) {
        v = v * 10 + c - '0';
        c = gc();
    }
    if (neg)
        v = -v;
    return true;
}

typedef pair<int, int> II;

const ld PI = acos(-1.0);
const ld eps = 1e-9;

const int dr[] = {+1, -1, 0, 0};
const int dc[] = {0, 0, +1, -1};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 205
#define maxv 2005
#define maxe 200005

struct HopcroftKarp {
    int nx, ny, E, adj[maxe], next[maxe], last[maxv], run[maxv], level[maxv], que[maxv], matx[maxv], maty[maxv];

    void init(int _nx, int _ny) {
        nx = _nx; ny = _ny;
        E = 0; ms(last, -1);
        ms(matx, -1); ms(maty, -1);
    }

    void add(int x, int y) {
        adj[E] = y; next[E] = last[x]; last[x] = E++;
    }

    bool bfs() {
        int qsize = 0;

        For(x, 1, nx) if (matx[x] != -1) level[x] = -1;
        else {
            level[x] = 0;
            que[qsize++] = x;
        }

        bool found = false;

        Rep(i, qsize) {
            for (int x = que[i], e = last[x]; e != -1; e = next[e]) {
                int y = adj[e];
                if (maty[y] == -1) found = true;
                else if (level[maty[y]] == -1) {
                    level[maty[y]] = level[x] + 1;
                    que[qsize++] = maty[y];
                }
            }
        }

        return found;
    }

    int dfs(int x) {
        for (int &e = run[x]; e != -1; e = next[e]) {
            int y = adj[e];
            if (maty[y] == -1 || (level[maty[y]] == level[x] + 1 && dfs(maty[y]))) {
                matx[x] = y;
                maty[y] = x;
                return 1;
            }
        }
        return 0;
    }

    int maxmat() {
        int total = 0;

        while (bfs()) {
            For(x, 1, nx) run[x] = last[x];
            For(x, 1, nx) if (matx[x] == -1) total += dfs(x);
        }

        return total;
    }
} hopkarp;

int can[maxn][maxn], l[maxn], r[maxn], n, m;

int  main()
{
//  freopen("in.txt", "r", stdin);
    scanf("%d %d", &n, &m);
    int id, u, v, t;
    ms(can, 1);
    For(i, 1, n) {
        l[i] = 1;
        r[i] = n;
    }
    Rep(run, m){
        scanf("%d %d %d %d", &id, &u, &v, &t);
        if(id == 1){
            For(i, 1, n) {
                if(i < u || i > v) can[i][t] = 0;
                else r[i] = min(r[i], t);
            }
        }
        else{
            For(i, 1, n){
                if(i < u || i > v) can[i][t] = 0;
                else l[i] = max(l[i], t);
            }
        }
    }

    hopkarp.init(n, n);
    For(i, 1, n){
        For(j, 1, n) if(j >= l[i] && j <= r[i] && can[i][j]){
            hopkarp.add(i, j);
        }
    }

    if(hopkarp.maxmat() < n){
        cout << -1;
        return 0;
    }

    For(i, 1, n) printf("%d%c", hopkarp.matx[i], i == n ? '\n' : ' ');

    return 0;
}