Pagini recente » Diferente pentru problema/towers intre reviziile 11 si 12 | Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Cod sursa (job #1470660)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
int N,K,dimrez;
int aib[100010],rez[100010];
inline int inversiuni(int);
int query(int);
void update(int,int);
int binarysearch(int);
int main()
{
f>>N>>K;
FOR (i,1,N) {
update(i,1);
}
int left=1,right=N;
//cout<<inversiuni(2);
while (left<right) {
int mij=(left+right)>>1;
//cout<<mij<<' '<<inversiuni(mij)<<'\n';
if (inversiuni(mij)<K) {
right=mij-1;
}
else if (inversiuni(mij)==K) {
left=mij;
break;
}
else {
left=mij+1;
}
}
if (inversiuni(left)<K) {
--left;
}
//cout<<left<<'\n';
FOR (i,1,left-1) {
rez[++dimrez]=i;
int poz=binarysearch(1);
update(poz,-1);
}
//cout<<query(N)<<'\n';
int i=left;
while (i<=N) {
int inver=inversiuni(i+1);
int nr=K-inver;
/*cout<<i<<' '<<K<<' '<<inver<<' '<<nr+1<<'\n';
FOR(j,1,N) {
cout<<j<<' '<<aib[j]<<'\n';
}
cout<<"\n";*/
int poz=binarysearch(nr+1);
rez[++dimrez]=poz;
update(poz,-1);
K-=nr;
++i;
}
if (dimrez<N) {
int poz=binarysearch(1);
rez[++dimrez]=poz;
update(poz,-1);
}
FOR (i,1,dimrez) {
g<<rez[i]<<' ';
}
f.close();g.close();
return 0;
}
inline int inversiuni(int x) {
int nr=N-x+1;
return nr*(nr-1)/2;
}
void update(int poz,int val) {
int C=0;
while (poz<=N) {
aib[poz]+=val;
while (!(poz&(1<<C))) {
++C;
}
poz+=(1<<C);
++C;
}
}
int query(int poz) {
int S=0,C=0;
while (poz) {
S+=aib[poz];
while (!(poz&(1<<C))) {
++C;
}
poz-=(1<<C);
++C;
}
return S;
}
int binarysearch(int poz) {
int left=1,right=N;
while (left<right) {
int mij=(left+right)>>1;
int val=query(mij);
if (val>=poz) {
right=mij;
}
else {
left=mij+1;
}
}
return left;
}