Cod sursa(job #2308251)

Utilizator BRIOI19Ben Test BRIOI19 Data 26 decembrie 2018 18:35:25
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN = 31000;
int n;
int curr;
int ans;
int finalans;
int pos = 1;
int tree[4*MAXN+10];
int num[4*MAXN+10];
void build(int node,int l,int r){
    if(l==r){
        tree[node] = curr;
        num[node] = 1;
        
    }else{
        int mid = (l+r)/2;
        if(mid>=curr){
            build(2*node,l,mid);
        }else{
            build(2*node+1,mid+1,r);
        }
        tree[node] = max(tree[2*node],tree[(2*node)+1]);
        num[node] = num[2*node]+num[(2*node)+1];
    
    }
    
}
void query(int node,int l,int r){
    if(l==r){
        tree[node] = 0;
        num[node] = 0;
        finalans = l;
    }else{
        int mid = (l+r)/2;
        if(ans+num[2*node]>=pos){
            query(2*node,l,mid);
        }else{
            ans+=num[2*node];
            
            query(2*node+1,mid+1,r);
        }
        tree[node] = max(tree[2*node],tree[(2*node)+1]);
        num[node] = num[2*node]+num[(2*node)+1];
        
    }
}
int main() {
    ifstream fin("order.in");
    ofstream fout("order.out");
    fin>>n;
	for(int i=1;i<=n;i++){
	    curr = i;
	    build(1,1,n);
	}

	int totallen = n;
	for(int i=1;i<=n;i++){
	    pos+=i;
	    pos%=totallen;
	    if(pos == 0){
	        pos = totallen;
	    }
	   
	    ans = 0;
	    query(1,1,n);
	    fout<<finalans<<" ";
	    totallen--;
	    pos--;
	}
}