| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1351611 | umbraphile | Art Collections (BOI22_art) | C++20 | 0 ms | 0 KiB |
/*author : umbraphile*/
#include <bits/stdc++.h>
#include "art.h"
using namespace std;
// #define int long long
#define kaneki ios::sync_with_stdio(0);cin.tie(nullptr)
#define TEST int t; cin >> t; while (t --)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(),a.rend()
#define mat vector<vector<int>>
const int MOD = 1e9 + 7;
const int inf = 2e18;
const int aura = LLONG_MIN;
const int MAXN = 1e5 + 5;
const int LOG = 20;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
// i dan j ga otish mumkun :
// if S_j <= E_i and E_i <= E_j
// x y kiritladi sen shortest path topasan xdan y ga yetib borish uchun
// maybe just dijkstra no weihgt yogu bfs?
int S[MAXN];
int E[MAXN];
// int dist[MAXN];
int par[MAXN];
// void solve()
// {
// int N,q; cin >> N >> q;
// for(int i = 1; i <= N; ++ i) cin >> S[i] >> E[i];
// while(q --)
// {
// int x, y; cin >> x >> y;
// if(x==y){cout << 0 << "\N";continue;}
// for(int i = 1; i <= N; ++ i) dist[i] = -1;
// queue<int> q;
// q.push(x);
// dist[x] = 0;
// bool ok = false;
// while(!q.empty())
// {
// int d = q.front();
// q.pop();
// if(d == y){cout << dist[d] << "\N";ok = true;break;}
// for(int i = 1; i <= N; ++ i){
// if(dist[i] == -1){
// if(S[i] <= E[d] && E[d] <= E[i])
// {
// dist[i] = dist[d] + 1;
// q.push(i);
// }
// }
// }
// }
// if(!ok) cout << "impossible\N";
// }
// }
// void solve()
// {
// int N,q; cin >> N >> q;
// vector<pair<int, int>> a;
// for(int i = 1; i <= N; ++ i){
// cin >> S[i] >> E[i];
// par[i] = -1;
// a.push_back({S[i],i});
// }
// sort(all(a));
// for(int i = 1; i <= N; ++ i)
// {
// for(int j = 0; j < N; ++ j)
// {
// // if(i == j) continue;
// int idx = a[j].second;
// if(idx == i) continue;
// // if(S[idx] <= E[i] && E[i] <= E[idx]){par[i] = idx;break;}
// // if(S[idx] > E[i]) break;
// // if(S[j] <= E[i] && E[i] <= E[j]){par[i] = j;break;}
// if(S[idx] > E[i]) break;
// if(E[idx] >= E[i]){par[i] = idx;break;}
// }
// }
// while(q --)
// {
// int x, y; cin >> x >> y;
// if(x==y){cout << 0 << "\N";continue;}
// int d = x;
// int cnt = 0;
// bool ok = false;
// for(int i = 0; i < N; ++ i)
// {
// d = par[d];
// if(d == -1) break;
// cnt ++;
// if(d == y){ok = true;break;}
// if(E[d] > E[y]) break;
// }
// if(ok) cout << cnt << "\N";
// else cout << "impossible\N";
// }
// }
// N ta son bor
// permutation top
// avval
// 1 2 3 4 5 .. N
// i uchun
// i 1 2 .. i - 1 i + 1 ... N -> first
// i sonni i - 1 indexdan 0 ga obkeganimda -1 ta sonni suradi
// x = i-1 ta sondan i dan kattalari soni
// y = i - 1 - x
// C_i = first - i qatnashgan inversiya + i create qigan inversion
// pos(i) = (C_i - first + (i - 1))/2
// int ask(vector<int> a){
// for(auto &r : a) cout << r << " ";
// int x; cin >> x;
// return x;
// }
void solve(int N)
{
// int N; cin >> N;
vector<pair<int, int>> a(N);
vector<int> b(N);
for(int i = 0; i < N; ++ i) b[i] = i + 1;
int first = publish(b);
for(int i = 1; i <= N; ++ i)
{
if(i == 1){a[0] = {0, 1};continue;}
vector<int> c;
c.push_back(i);
for(int j = 1; j <= N; ++ j)
{
if(i == j) continue;
c.push_back(j);
}
int c_i = publish(c);
int x = (c_i - first + (i - 1)) / 2;
// cout << x << " " << i << "\N";
a[i-1] = {x, i};
}
sort(all(a));
vector<int> ans(N);
for(int i = 0; i < N; ++ i) ans[i] = a[i].second;
// for(auto &r : ans) cout << r << " ";
answer(ans);
}
signed main()
{
//#ifndef LOCAL
//freopen("input.txt", "mx", stdin);
//freopen("output.txt", "x", stdout);
//#endif
kaneki;
// pre();
// sieve();
solve();
}