Cod sursa(job #3245850)

Utilizator MihneaStoicaMihnea Teodor Stoica MihneaStoica Data 30 septembrie 2024 21:13:17
Problema Order Scor 55
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.92 kb
// "I am the true mogger."
// 					-MihneaTheMogger
// 
// prob Order
// 
// tl 25
// ml 64
// 
// LOT

#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(false);\
                               cin.tie(nullptr);\
                 			  cout.tie(nullptr);
using namespace std;

#define int int64_t 
#define YES cout<<"YES"    
#define YESn cout<<"YES\n" 
#define NO cout<<"NO"     
#define NOn cout<<"NO\n"       

#define MORE_TESTS 0    
#define FASTIO 1     
int32_t TESTCASE_COUNT = 1, TESTCASE;

const int lim = 3e4 + 1;
int aint[lim * 4], n;

void update (int nod, int st, int dr, int pos)
{
	if (st == dr) {
		aint[nod] = 1;
		return;
	}
	else {
		int mid = (st + dr) / 2;
		if (pos <= mid) {
			update (nod * 2 + 1, st, mid, pos);
		}
		else {
			update (nod * 2 + 2, mid + 1, dr, pos);
		}
		aint[nod] = aint[nod * 2 + 1] + aint[nod * 2 + 2];
	}
}

int query (int nod, int st, int dr, int l, int r)
{
	if (r < st || l > dr) {
		return 0;
	}
	if (l <= st && dr <= r) {
		return aint[nod];
	}
	else {
		int mid = (st + dr) / 2;
		return query(nod * 2 + 1, st, mid, l, r) + query(nod * 2 + 2, mid + 1, dr, l, r);
	}
}

void advanc (int &pos, int i)
{
	while (i > 0) {
		int st = pos + 1, dr = pos + i;
		if (dr > n) {
			dr -= n;
		}
		
		int sum = (st <= dr ? query(1, 1, n, st, dr) : query(1, 1, n, st, n) + query(1, 1, n, 1, dr));
		pos += i;
		if (pos > n) {
			pos -= n;
		}
		i = sum;
	}
}

void Solve ()
{
#ifndef LOCAL
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);
#endif
	
	cin >> n;
	
	int pos = 1;
	for (int i = 1; i <= n; i ++) {
		advanc (pos, i);
		update (1, 1, n, pos);
		cout << pos << " ";
	}
	cout << '\n';
}

/*

*/

int32_t main ()
{
    #if FASTIO == 1
    FastIO;
    #endif
    #if MORE_TESTS == 1
    cin >> TESTCASE_COUNT;
    #endif
    for (TESTCASE = 1; TESTCASE <= TESTCASE_COUNT; TESTCASE ++)
        Solve ();
}

/*
___  ___          _        ______         ___  ____ _                    _____ _         ___  ___
|  \/  |         | |       | ___ \        |  \/  (_) |                  |_   _| |        |  \/  |
| .  . | __ _  __| | ___   | |_/ /_   _   | .  . |_| |__  _ __   ___  __ _| | | |__   ___| .  . | ___   __ _  __ _  ___ _ __
| |\/| |/ _` |/ _` |/ _ \  | ___ \ | | |  | |\/| | | '_ \| '_ \ / _ \/ _` | | | '_ \ / _ \ |\/| |/ _ \ / _` |/ _` |/ _ \ '__|
| |  | | (_| | (_| |  __/  | |_/ / |_| |  | |  | | | | | | | | |  __/ (_| | | | | | |  __/ |  | | (_) | (_| | (_| |  __/ |
\_|  |_/\__,_|\__,_|\___|  \____/ \__, |  \_|  |_/_|_| |_|_| |_|\___|\__,_\_/ |_| |_|\___\_|  |_/\___/ \__, |\__, |\___|_|
                                   __/ |                                                                __/ | __/ |
                                  |___/                                                                |___/ |___/
*/