#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
typedef pair<ll, ll> llp;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
ll N;
ll arr[400];
vector<pair<double, llp> > V;
int ans[400];
void makeitgood() {
set<double> S;
for (int i = 0; i < V.size(); i++) {
S.insert(V[i].first);
}
double cnt = 0.0;
map<double, double> M;
while (!S.empty()) {
M[*S.begin()] = cnt;
S.erase(S.begin());
cnt += 1.0;
}
for (int i = 0; i < V.size(); i++) {
V[i].first = M[ V[i].first ];
}
}
int main(int argc, char **argv) {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
if (N > 400) exit(-1);
for (int i = 0; i < N; i++) cin >> arr[i];
V.pb(mp(0.0, mp(0, -1)));
V.pb(mp(1.0, mp(0, -1)));
for (int i = 0; i < N; i++) {
/*for (int k = 0; k < V.size(); k++) {
cerr << V[k].first << " " << V[k].second.first << " " << V[k].second.second << endl;
} cerr << endl;*/
ll d = (i?arr[i]-arr[i-1]:arr[i]);
ll presum = 0;
int ptr = 0;
while (presum + 1 != d) {
//cerr << presum+1 << " " << d << endl;
presum += V[ptr].second.first;
ptr++;
}
if (ptr != 0) ptr--;
double key = (V[ptr].first + V[ptr+1].first) / 2.0;
//cerr << "inserting with key: " << key << " " << V[ptr].first << " - " << V[ptr+1].first << " . " << ptr << endl;
V.insert(V.begin()+ptr+1, mp(key, mp(d, i)));
sort(V.begin(), V.end());
if (i % 10 == 0) {
makeitgood();
}
}
/*for (int k = 0; k < V.size(); k++) {
cerr << V[k].first << " " << V[k].second.first << " " << V[k].second.second << endl;
} cerr << endl;*/
makeitgood();
for (int i = 0; i < V.size(); i++) {
if (V[i].second.second != -1) ans[ V[i].second.second ] = V[i].first;
}
for (int i = 0; i < N; i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
Compilation message
permutation.cpp: In function 'void makeitgood()':
permutation.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < V.size(); i++) {
~~^~~~~~~~~~
permutation.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < V.size(); i++) {
~~^~~~~~~~~~
permutation.cpp: In function 'int main(int, char**)':
permutation.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < V.size(); i++) {
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
484 KB |
Output is correct |
| 3 |
Runtime error |
3 ms |
484 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
484 KB |
Output is correct |
| 3 |
Runtime error |
3 ms |
484 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
484 KB |
Output is correct |
| 3 |
Runtime error |
3 ms |
484 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
484 KB |
Output is correct |
| 3 |
Runtime error |
3 ms |
484 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
484 KB |
Output is correct |
| 3 |
Runtime error |
3 ms |
484 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
7 ms |
484 KB |
Output is correct |
| 3 |
Runtime error |
3 ms |
484 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
