| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 13981 |
2015-04-24T17:42:17 Z |
kriii |
버블 정렬 (OJUZ10_bubblesort) |
C++14 |
|
84 ms |
4424 KB |
#include <stdio.h>
#include <algorithm>
using namespace std;
int N,K;
struct pos{
int x,i;
bool operator <(const pos t) const{
if (x == t.x) return i < t.i;
return x < t.x;
}
}P[100005];
const int Z = 1<<17;
int it[2][Z*2],A[Z];
int sum(int *it, int y)
{
int s = 0;
int x = Z; y += Z;
while (x < y){
if (x & 1) s += it[x++];
if (~y & 1) s += it[y--];
x /= 2; y /= 2;
} if (x == y) s += it[x];
return s;
}
int trace(int *it, int x)
{
int s = 1;
while (s < Z){
s *= 2;
if (it[s] <= x){
x -= it[s];
s++;
}
}
return s - Z;
}
void del(int *it, int x)
{
x += Z;
while (x){
it[x]--;
x /= 2;
}
}
int main()
{
scanf ("%d %d",&N,&K);
for (int i=0;i<N;i++){
scanf ("%d",&P[i].x);
P[i].i = i;
}
sort(P,P+N);
for (int k=0;k<2;k++){
for (int i=0;i<N;i++) it[k][i+Z] = 1;
for (int j=Z-1;j>=1;j--) it[k][j] = it[k][j*2] + it[k][j*2+1];
}
for (int i=0;i<N;i++){
int u = max(0,sum(it[0],P[i].i)-K-1);
int x = trace(it[1],u);
A[x] = P[i].x;
del(it[0],P[i].i);
del(it[1],x);
}
for (int i=0;i<N;i++){
printf ("%d ",A[i]);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 4 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 5 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 7 |
Correct |
0 ms |
4424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4424 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 4 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4424 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4424 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 9 |
Correct |
0 ms |
4424 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
4424 KB |
Output is correct |
| 2 |
Correct |
68 ms |
4424 KB |
Output is correct |
| 3 |
Correct |
70 ms |
4424 KB |
Output is correct |
| 4 |
Correct |
66 ms |
4424 KB |
Output is correct |
| 5 |
Correct |
24 ms |
4424 KB |
Output is correct |
| 6 |
Correct |
64 ms |
4424 KB |
Output is correct |
| 7 |
Correct |
75 ms |
4424 KB |
Output is correct |
| 8 |
Correct |
63 ms |
4424 KB |
Output is correct |
| 9 |
Correct |
64 ms |
4424 KB |
Output is correct |
| 10 |
Correct |
54 ms |
4424 KB |
Output is correct |
| 11 |
Correct |
76 ms |
4424 KB |
Output is correct |
| 12 |
Correct |
61 ms |
4424 KB |
Output is correct |
| 13 |
Correct |
84 ms |
4424 KB |
Output is correct |
| 14 |
Correct |
41 ms |
4424 KB |
Output is correct |
| 15 |
Correct |
61 ms |
4424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
4424 KB |
Output is correct |
| 2 |
Correct |
59 ms |
4424 KB |
Output is correct |
| 3 |
Correct |
62 ms |
4424 KB |
Output is correct |
| 4 |
Correct |
43 ms |
4424 KB |
Output is correct |
| 5 |
Correct |
66 ms |
4424 KB |
Output is correct |
| 6 |
Correct |
63 ms |
4424 KB |
Output is correct |
| 7 |
Correct |
77 ms |
4424 KB |
Output is correct |
| 8 |
Correct |
65 ms |
4424 KB |
Output is correct |
| 9 |
Correct |
25 ms |
4424 KB |
Output is correct |
| 10 |
Correct |
65 ms |
4424 KB |
Output is correct |
| 11 |
Correct |
65 ms |
4424 KB |
Output is correct |
| 12 |
Correct |
60 ms |
4424 KB |
Output is correct |
| 13 |
Correct |
63 ms |
4424 KB |
Output is correct |
| 14 |
Correct |
73 ms |
4424 KB |
Output is correct |
| 15 |
Correct |
68 ms |
4424 KB |
Output is correct |
