Nu aveti permisiuni pentru a descarca fisierul grader_test74.in
Cod sursa(job #1792171)
| Utilizator | Data | 30 octombrie 2016 09:43:50 | |
|---|---|---|---|
| Problema | Order | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 1.17 kb |
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
const int MAXN = 30005;
int N;
int aib[MAXN];
int poz;
void Update( int p, int x );
int Sum( int p );
int main()
{
int i, j, st, dr, mij;
fin >> N;
for ( i = 1; i <= N; i++ )
Update(i, 1);
poz = 2;
for ( i = 1; i <= N; i++ )
{
poz = ( poz + i - 1 ) % ( N - i + 1 );
if ( poz == 0 ) poz = N - i + 1;
st = 1, dr = N;
while ( st <= dr )
{
mij = ( st + dr ) / 2;
if ( Sum(mij) >= poz )
{
if ( Sum(mij) == poz )
{
j = mij;
}
dr = mij - 1;
}
else
st = mij + 1;
}
Update(j, -1);
fout << j << ' ';
}
fin.close();
fout.close();
return 0;
}
void Update( int p, int x )
{
for ( int i = p; i <= N; i += i & -i )
aib[i] += x;
}
int Sum( int p )
{
int s = 0;
for ( int i = p; i >= 1; i -= i & -i )
s += aib[i];
return s;
}
