oj.uz

답안 #573521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
573521 2022-06-06T18:48:33 Z neonaht 순열 (APIO22_perm) C++17
100 / 100
 2 ms 340 KB 
#include "perm.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int SZ=207;
int fen[SZ];

void update(int x,int val) {
	while(x<SZ) {
		fen[x]+=val;
		x+=(x&-x);
	}
	return ;
}

int query(int x) {
	int sum(0);
	while(x) {
		sum+=fen[x];
		x-=(x&-x);
	}
	return sum;
}

std::vector<int> construct_permutation(long long k)
{
	for(int i=0;i<SZ;i++) fen[i]=0;
	if(k==2) return {0};
	--k;
	vector <int> res,seq;
	ll cnt(0),v(2),z=k;
	int maxi(0);
	while(z) {
		++cnt;
		z>>=1LL;
	}
	--cnt;
	for(int i=1;i<=cnt;i++) update(i,1);
	seq.emplace_back(1);
	ll Bit=(1LL<<(cnt-1));
	bool chx=true;
	while(Bit) {
		if(chx) {
			if(k&Bit) {
				if(v>cnt) seq.insert(seq.begin(),query(v-1)+1);
				else seq.insert(seq.begin(),query(v));
				update(v,1);
				chx=false;
			}
			++v;
			Bit>>=1LL;
		}else {
			if(k&Bit && k&(Bit>>1LL)) {
				if(v+1>cnt) seq.insert(seq.begin()+2,query(v)+1);
				else seq.insert(seq.begin()+2,query(v+1));
				update(v+1,1);
			}else if(k&Bit) {
				if(v>cnt) seq.insert(seq.begin(),query(v-1)+1);
				else seq.insert(seq.begin(),query(v));
				update(v,1);
			}else if(k&(Bit>>1LL)) {
				if(v+1>cnt) seq.insert(seq.begin(),query(v)+1);
				else seq.insert(seq.begin(),query(v+1));
				update(v+1,1);
			}
			v+=2;
			Bit>>=2LL;
		}
	}
	for(auto x:seq) maxi=max(maxi,x);
	for(int i=2;i<=cnt;i++) maxi=max(maxi,query(i));
	res.emplace_back(maxi);
	for(auto x:seq) res.emplace_back(x-1);
	for(int i=2;i<=cnt;i++) res.emplace_back(query(i)-1);
	return res;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
90.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 300 KB Output is correct
6 Correct 2 ms 296 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 276 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct