This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
int N, Q;
vi A;
vi B;
ll ans;
vi P;
vi answerPermutation;
ll eval(vi &foo)
{
ll ret = 0;
for (int l = 0; l < sz(foo); ++l)
for (int r = l + 1; r <= sz(foo); ++r)
{
int tmp = -1;
for (int i = l; i < r; ++i)
if (foo[i] != tmp)
++ret, tmp = foo[i];
}
return ret;
}
void bf(int idx)
{
if (idx == sz(B))
{
ll tmpans = eval(P);
if (tmpans < ans)
{
ans = tmpans;
answerPermutation = P;
}
}
for (int j = 0; j < sz(B); ++j)
{
if (P[j] == -1)
{
P[j] = B[idx];
bf(idx + 1);
P[j] = -1;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> Q;
A.resize(N);
for (int i = 0; i < N; ++i)
cin >> A[i];
while (Q--)
{
int lx, rx;
cin >> lx >> rx;
--lx;
B = vi(A.begin() + lx, A.begin() + rx);
ans = INT_MAX;
P.assign(sz(B), -1);
bf(0);
sort(all(B));
ll sortans = 0;
for (int l = 0; l < sz(B); ++l)
for (int r = l + 1; r <= sz(B); ++r)
{
int tmp = -1;
for (int i = l; i < r; ++i)
if (B[i] != tmp)
++sortans, tmp = B[i];
}
// cout << "\n";
cout << ans << "\n";
// for (int x : answerPermutation)
// cout << x << " ";
// cout << '\n';
// cout << sortans << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |