[ Winner!! ] (1000pts)

 : gs12065, gs12117

Gold Medal List!! (cutline 1000pts)

  : gs12117, gs12065

Silver Medal List (cutline 707pts)

  : ainta, tncks0121, gs12120

Bronze Medal List (cutline 447pts)

  : gs13003, gs11028, pl0892029, gs12016, gs11103, gs12013, ajou709

#include<stdio.h>
int n,w[20001],i,IT[70000],l,R[20001],B,E,M,S;
int find(int p){
	B=l,E=l+p,S=0;
	while(B<=E){
		if(B&1)S+=IT[B];
		if(!(E&1))S+=IT[E];
		B=(B+1)/2,E=(E-1)/2;
	}
	return S;
}
int main()
{
	int b,e,m,t;
	scanf("%d",&n);
	l=1;
	while(l<n)l*=2;
	for(i=0;i<n;i++){
		scanf("%d",&w[i]);
		t=i+l;while(t)IT[t]++,t/=2;}
	for(i=n-1;i>=0;i--){
		b=0,e=n-1;
		while(b<=e){
			m=(b+e+1)/2;
			if(IT[m+l]==0){
				if(find(m)>=w[i])e=m-1;
				else b=m+1;}
			else{
				t=find(m);
				if(t==w[i])break;
				if(t<w[i])b=m+1;
				else e=m-1;
			}
		}
		R[m]=i;
		t=m+l;while(t)IT[t]--,t/=2;
	}
	for(i=0;i<n;i++)printf("%d\n",R[i]+1);
}

#include<stdio.h>
#include<string.h>

#define N_ 20000
#define bl 145

int N;
int bucket[bl+1][bl*2+1], bn;
int cnt[bl+1];

int tmp[N_+1], tn;
int chk;
void replace(){
	int i, j; tn = 0;
	for(i=1; i<=bl; i++){
		for(j=1; j<=cnt[i]; j++) tmp[++tn] = bucket[i][j];
		cnt[i] = 0;
	}
	j = 1; bn = 1;
	for(i=1; i<=tn; i++){
		bucket[bn][++cnt[bn]] = tmp[i];
		if(cnt[bn] == bl) j++;
	}
}

void insert(int rank, int dat){
	int bx, by = rank, i;
	for(bx=1; bx<=bn; bx++){
		if(by > cnt[bx]) by -= cnt[bx];
		else break;
	} if(bx > bn) bx = bn, by = cnt[bn]+1;
	for(i=++cnt[bx]; i>by; i--) bucket[bx][i] = bucket[bx][i-1];
	bucket[bx][by] = dat;
}

int main(){
	int i, j;
	scanf("%d",&N); bn = 1;
	for(i=1; i<=N; i++){
		int d; scanf("%d",&d); ++chk;
		if(i == 1) bucket[1][1] = i, cnt[1] = 1;
		else{
			insert(d,i); 
			if(chk == bl) replace(), chk=0;
		}
	}

	for(i=1; i<=bl; i++) for(j=1; j<=cnt[i]; j++){
		printf("%d\n",bucket[i][j]);
	}
	return 0;
}

#include<stdio.h>
#include<list>
using namespace std;

int main(void)
{
    int n, rank=0, i;
    list<int> L;
    list<int>::iterator iter;
    scanf("%d", &n);
    for( i = 1, iter = L.begin() ; i <= n ; i++ )
    {
        int prev = rank;
        scanf("%d", &rank);
        prev = rank-prev;
        if( prev < rank ) advance(iter, prev-1);
        else iter=L.begin(), advance(iter, rank-1);
        L.insert(iter, i);
    }
    for( iter = L.begin() ; iter != L.end() ; iter++ )
        printf("%d\n", *iter);
    return 0;
}

#include <cstdio>

int main()
{
	int n;
	scanf("%d",&n);
	printf("%lld",(long long)((n+1)*(n+1)/2-1)%1000000007);
}

#include<stdio.h>
long long A[10],B[10],K=1000000000,R,T,X,a,b,c,d,e,f,g,h,t1,t2,t3,t4,x,y;
int i,n;
void PP(int N){
	X=1,a=1,b=0,c=0,d=1,e=4,f=1,g=4,h=0;
	while(N){
		if(N&X){
			t1=a*e+b*g,t2=a*f+b*h,t3=c*e+d*g,t4=c*f+d*h;
			t1%=K,t2%=K,t3%=K,t4%=K;a=t1,b=t2,c=t3,d=t4;N-=X;}
		t1=e*e+f*g,t2=e*f+f*h,t3=g*e+h*g,t4=g*f+h*h;
		t1%=K,t2%=K,t3%=K,t4%=K;e=t1,f=t2,g=t3,h=t4;X*=2;}}
int main()
{
	A[1]=B[2]=1,B[3]=7,A[2]=4,A[3]=14,A[4]=68,B[4]=34;
	scanf("%d",&n);
	if(n<=6){
		for(i=5;i<=n;i++){
			A[i]=(A[i-1]+A[i-2])*4;
			B[i]=A[i]/2;
			A[i]%=K,B[i]%=K;}
		printf("%lld\n",(A[n-1]+B[n-1]*2+2*(A[n-2]+2*B[n-2]))%K);}
	else{
		R=68,T=14;
		PP(n-5);
		x=(R*a+T*c)%K;
		PP(n-6);
		y=(R*a+T*c)%K;
		printf("%lld\n",(x*2+y*4)%K);
	}
}

#include <cstdio>

#define MOD 1000000000
#define ll long long

int n;
ll first[6]={1,0,0,1,1,0}, res[6], recur[6][6]={
	0,1,0,1,0,1,
	0,1,1,1,0,1,
	0,1,0,1,0,1,
	1,2,0,2,1,2,
	0,1,0,1,0,1,
	0,1,1,1,0,1
};

void multiply(ll f[6][6], ll s[6][6], ll r[6][6]){
	int i, j, k;
	for(i=0; i<6; i++){
		for(j=0; j<6; j++){
			r[i][j] = 0;
			for(k=0; k<6; k++){
				r[i][j] += f[i][k]*s[k][j];
				if(r[i][j] >= MOD) r[i][j] %= MOD;
			}
		}
	}
}

void copy(ll f[6][6], ll s[6][6]){
	int i, j;
	for(i=0; i<6; i++){
		for(j=0; j<6; j++){
			s[i][j] = f[i][j];
		}
	}
}

void solve(){
	int t=1;
	while((t<<1) <= n) t = t<<1;

	ll now[6][6]={
		1,0,0,0,0,0,
		0,1,0,0,0,0,
		0,0,1,0,0,0,
		0,0,0,1,0,0,
		0,0,0,0,1,0,
		0,0,0,0,0,1
	}, tmp[6][6];

	while(t){
		multiply(now, now, tmp);
		copy(tmp, now);
		if(n&t){
			multiply(now, recur, tmp);
			copy(tmp, now);
		}
		t = t>>1;
	}

	int i, j;
	for(i=0; i<6; i++){
		res[i] = 0;
		for(j=0; j<6; j++){
			res[i] += first[j]*now[i][j];
			if(res[i] >= MOD) res[i] %= MOD;
		}
	}
}

int main(){
	scanf("%d", &n);
	n--;

	solve();

	printf("%lld\n", (res[1]-res[2]+res[5]+MOD)%MOD);
	
	return 0;
}

#include<stdio.h>
#include<queue>
std::priority_queue<int> a;
int m[300100][2];
int tmp[300100][2];
int left[300100],p;
int n;
void sort(int start,int end){
	if(end<start+2)return;
	int mid=(start+end)/2;
	sort(start,mid);
	sort(mid,end);
	int i,j,k;
	i=start;
	j=mid;
	k=start;
	for(;i<mid&&j<end;k++){
		if(m[i][1]>m[j][1]){
			tmp[k][0]=m[i][0];
			tmp[k][1]=m[i][1];
			i++;
		}
		else{
			tmp[k][0]=m[j][0];
			tmp[k][1]=m[j][1];
			j++;
		}
	}
	for(;i<mid;i++){
		tmp[k][0]=m[i][0];
		tmp[k][1]=m[i][1];
		k++;
	}
	for(i=start;i<k;i++){
		m[i][0]=tmp[i][0];
		m[i][1]=tmp[i][1];
	}
}
int main(){
	scanf("%d",&n);
	int i,ans,siz;
	long long int total;
	for(i=0;i<n;i++){
		scanf("%d%d",&m[i][0],&m[i][1]);
	}
	sort(0,n);
	for(total=siz=ans=i=0;i<n;i++){
		a.push(m[i][0]);
		siz++;
		total+=m[i][0];
		while(p&&total<=(long long int)siz*m[i][1]){
			p--;
			a.push(left[p]);
			siz++;
			total+=left[p];
		}
		if(total>(long long int)siz*m[i][1]){
			left[p]=a.top();
			p++;
			total-=a.top();
			a.pop();
			siz--;
		}
		if(siz>ans){
			ans=siz;
		}
	}
	printf("%d",ans);
}