#include <bits/stdc++.h>
#define file ""
#define all(x) x.begin(), x.end()
#define sc second
#define fr first
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;
const int N = 1e5 + 5;
int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};
int n;
int a[N], l[N];
vector<int> t(N * 4, 1e9);
void update(int u, int l, int r, int pos, int val) {
if (l == r) {
t[u] = val;
return;
}
int m = l + r >> 1;
if (pos <= m) update(u + u, l, m, pos, val);
else update (u + u + 1, m + 1, r, pos, val);
t[u] = min(t[u + u], t[u + u + 1]);
}
int get(int u, int ul, int ur, int l, int r) {
if (l > ur || ul > r) return 1e9;
if (l <= ul && ur <= r) return t[u];
int um = ul + ur >> 1;
return min(get(u + u, ul, um, l, r), get(u + u + 1, um + 1, ur, l, r));
}
int solve1() {
int res = 40;
for (int mask = 1; mask < (1 << n); mask += 2) {
//cerr << mask << endl;
vector<int> v[20];
int cur = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) v[++cur].pb(a[i + 1]);
else v[cur].pb(a[i + 1]);
}
vector<int> ans;
for (int to : v[1]) ans.pb(to);
if (!is_sorted(all(ans))) continue;
for (int i = 2; i <= cur; i++) {
//cerr << "i : " << i << endl;
for (int p = 0; p <= ans.size(); p++) {
vector<int> d = ans;
//cerr << "p : " << p << endl;
for (int j = 0; j < v[i].size(); j++)
d.insert(d.begin() + p + j, v[i][j]);
//for (int to : d) cerr << to << " ";
//cerr << endl;
if (is_sorted(all(d))) {
ans = d;
goto pos;
}
}
goto here;
pos:;
}
res = min(res, cur);
here:;
}
return res;
}
int solve2() {
vector<int> dp(n + 5);
l[1] = 1;
int last = 1;
for (int i = 2; i <= n; i++) {
if (a[i] >= a[i - 1]) continue;
else {
for (int p = last; p <= i - 1; p++)
l[p] = last;
last = i;
}
}
for (int p = last; p <= n; p++) l[p] = last;
update(1, 1, n, 1, 0);
dp[1] = 1;
for (int i = 2; i <= n; i++) {
update(1, 1, n, i, dp[i - 1]);
dp[i] = get(1, 1, n, l[i] + 1, i) + 1;
int rgt = l[i] - 1;
int left = l[l[i]];
if (rgt == 0) dp[i] = min(dp[i], 1);
}
for (int i = 1; i <= n; i++)
update(1, 1, n, i, 1e9);
return dp[n];
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
srand(time(nullptr));
while (true) {
n = rand() % 10 + 1;
for (int i = 1; i <= n; i++) a[i] = rand() % 8 + 1;
if (solve1() != solve2()) {
cout << n << "\n";
for (int i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
cout << solve1() << " " << solve2() << endl;
break;
}
else cerr << "ok\n";
}
return 0;
}
Compilation message
money.cpp: In function 'void update(int, int, int, int, int)':
money.cpp:35:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m = l + r >> 1;
| ~~^~~
money.cpp: In function 'int get(int, int, int, int, int)':
money.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int um = ul + ur >> 1;
| ~~~^~~~
money.cpp: In function 'int solve1()':
money.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int p = 0; p <= ans.size(); p++) {
| ~~^~~~~~~~~~~~~
money.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int j = 0; j < v[i].size(); j++)
| ~~^~~~~~~~~~~~~
money.cpp: In function 'int solve2()':
money.cpp:105:8: warning: unused variable 'left' [-Wunused-variable]
105 | int left = l[l[i]];
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
