Kaosar və M(ex+od)#12362

Kaosar və M(ex+od) (Həll təhlili)

Problem Müəllifi:	Al Kaosar Hussain
Hazırlayan:	Al Kaosar Hussain

Həll

Bu problemin əsas müşahidəsi $i mod i + 1 = i$ i\mod i+1=i olmasıdır.

İndi bu problem bir çox yolla həll edilə bilər, burada biri var. $k = 0, 1$ k=0,1 üçün iki əsas hal var.

$k = 0$ k=0 üçün bir etibarlı həll $1, 2, .., n$ 1,2,..,n və $k = 1$ k=1 üçün bir etibarlı həll $2, 3, ... n, 1$ 2,3,...n,1 dir və $n < k$ n<k üçün

heç bir etibarlı permutasiya yoxdur.

Ümumi hal budur ki, əgər $p$ -nin əvvəlində $k$ -ni daxil etsək, onda ədədlər

$1, 2, .., k - 1, k + 1, .., n$ 1,2,..,k-1,k+1,..,n olacaq, onda $p mod 1$ p\mod 1 $0$ verəcək və $1 mod 2$ 1\mod 2, $2 mod 3$ 2\mod 3,.., $k - 1 mod k + 1$ k-1\mod k+1

$1, 2, 3, ..., k - 1$ 1,2,3,...,k-1 verəcək və mex tam olaraq $k$ -ya çevriləcək ki, bu da bu problem üçün optimal həlldir.

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

#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        ll k;
        cin >> n >> k;
        if (k >= n) {
            cout << -1 <<end;
            continue;
        }
        if (k == 0) {
            rep(i, 1, n + 1) cout << i <<  " ";
            cout <<endl;
        } else if (k == 1) {
            rep(i, 2, n + 1) cout << i << " ";
            cout << 1 <<endl;
        } else {
            vi ans;
            ans.push_back((int)k);
            rep(i, 1, n + 1) {
                if (i != k) ans.push_back(i);
            }
            rep(i, 0, n) {
                cout << ans[i] <<  " ";
            }
            cout <<endl;
        }
    }

    return 0;
}

C++