Pagini recente » Cod sursa (job #2278400) | Cod sursa (job #1491983) | Monitorul de evaluare | Cod sursa (job #1186909) | Cod sursa (job #2612307)
/*#include<bits/stdc++.h>
#define N (int)1e5+5
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m,t;
cin>>n>>m;
int v[n],viz[N],dp[n];
memset(viz,0,sizeof(viz));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;++i)
cin>>v[i];
dp[n-1]=1;
viz[v[n-1]]=1;
for(int i=n-2;i>=0;--i)
{
if(!viz[v[i]])
{
viz[v[i]]=1;
dp[i]=dp[i+1]+1;
}
else
dp[i]=dp[i+1];
}
for(int i=1;i<=m;++i)
{
cin>>t;
cout<<dp[t-1]<<'\n';
}
}*/
//Ksecv
/*#include<bits/stdc++.h>
#define N 100003
using namespace std;
int n,k,v[N],dp[2][N];
int s[N];
void read()
{
ifstream fin("ksecv.in");
fin>>n>>k;
for(int i=0;i<n;++i)
fin>>v[i];
fin.close();
}
int main()
{
read();
bool pas=0;
dp[0][0]=dp[0][1]=1e9;
dp[1][0]=v[0];
for(int j=1;j<n;++j)
{
dp[0][j]=1e9;
dp[1][j]=max(dp[1][j-1],v[j]);
}
//cout<<dp[1][n-1];
//dinamica in n*k
//dp(i)(j)=min(dp(i-1)(l)+max(l+1 ... j)) dupa l de la 1 la j-1
//i de la 1 la k
//j de la 1 la n
for(int i=1;i<k;++i,pas=1-pas)
{
for(int j=0;j<n;++j)
dp[pas][j]=1e9;
//stack<int> s;
int stop=1;
s[stop]=0;
//in stiva imi pastrez indicii din v ai maximelor(l-ul din formula)
//stiva va contine un sir descrescator de valori ( de fapt indicii lor )
//fiecare valoare din stiva este un reprezentant pentru fiecare secventa
for(int j=1;j<n;++j)
{
//if(stop>0)
while(stop>0 && v[j]>=v[s[stop]])
{
dp[pas][j]=min(dp[pas][j],dp[1-pas][s[stop]]+v[j]);
//daca avem o situatie de tipul:
// (..)(..)...(...)(...v[s[stop]]...)->urmeaza v[j] care e mai mare, trebuie actualizat numarul
dp[pas][j]=min(dp[pas][j],dp[pas][s[stop]]-v[s[stop]]+v[j]);
--stop;
if(!stop)
break;
}
//daca nu e maximul pana in prezent:
if(stop>0)
{
//daca incepem o noua secventa dinainte de la un indice <= s[stop]
dp[pas][j]=min(dp[pas][j],dp[pas][s[stop]]);
//daca incep de la s[stop]+1 (de indice mai mare am verificat mai sus
dp[pas][j]=min(dp[pas][j],dp[1-pas][s[stop]]+v[j]);
}
++stop;
s[stop]=j;
}
}
ofstream fout("ksecv.out");
fout<<dp[k&1][n-1]<<'\n';
fout.close();
}*/
//Order
#include<bits/stdc++.h>
using namespace std;
int st[120000];
ofstream fout("order.out");
int getMid(int s, int e)
{
return s+(e-s)/2;
}
void build(int node,int s,int d)
{
if(s==d)
{
st[node]=1;
return;
}
build(2*node,s,getMid(s,d));
build(2*node+1,getMid(s,d)+1,d);
st[node]=st[2*node]+st[2*node+1];
return;
}
void del(int node,int s,int d,int x)
{
if(s==d)
{
fout<<s<<' ';
st[node]=0;
return;
}
//cout<<s<<' '<<d<<' '<<st[2*node]<<'\n';
if(st[2*node]>=x)
{
del(2*node,s,getMid(s,d),x);
st[node]=st[2*node]+st[2*node+1];
return;
}
del(2*node+1,getMid(s,d)+1,d,x-st[2*node]);
st[node]=st[2*node]+st[2*node+1];
return;
}
int main()
{
int n,k;
ifstream fin("order.in");
fin>>n;
fin.close();
k=n;
build(1,1,n);
int sters=2;
for(int i=0;i<n;++i)
{
del(1,1,n,sters);
--k;
if(k>0)
{
sters+=i;
//in sters imi retin al catelea 1 trebuie sters din arborele de intervale
++sters;
sters%=k;
if(!sters)
sters=k;
//cout<<<<sters<<' ';
}
}
fout.close();
}