QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#307626 | #962. Thanks to MikeMirzayanov | yllcm | WA | 1ms | 3772kb | C++14 | 2.8kb | 2024-01-18 21:53:41 | 2024-01-18 21:53:42 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
int x = 0; bool op = false;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar();
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 2e4 + 10;
int n, type;
int a[N];
vector<vector<int>> ans;
void doit(vector<int> d) {
// if(type)reverse(d.begin(), d.end());
int sum = 0;
for(int u : d)reverse(a + 1 + sum, a + 1 + sum + u), sum += u;
if(type)reverse(d.begin(), d.end());
ans.pb(d); type ^= 1;
return ;
}
int main() {
n = read();
for(int i = 1; i <= n; i++)a[i] = read();
vector<int> rg = {n};
for(int w = 15; ~w; w--) {
vector<int> d;
auto work = [&](int l, int r) {
// cerr << "work:" << l << ' ' << r << endl;
vector<int> seq;
for(int i = l; i <= r; i++) {
int k = i;
while(k < r && (a[k + 1] >> w & 1) == (a[k] >> w & 1))k++;
seq.pb(k - i + 1); i = k;
}
// cerr << seq.size() << endl;
if(seq.size() == 1)return d.pb(seq[0]), seq[0];
if(seq.size() == 2) {
if(a[l] >> w & 1)return d.pb(seq[0] + seq[1]), -1;
else return d.pb(seq[0]), d.pb(seq[1]), seq[0];
}
if(seq.size() == 3) {
if(a[l] >> w & 1)d.pb(seq[0] + seq[1]), d.pb(seq[2]);
else d.pb(seq[0]), d.pb(seq[1] + seq[2]);
}
else {
int o = 0;
for(int i = 0; i < seq.size(); i += 2, o ^= 1) {
if(i + 1 < seq.size() && o)d.pb(seq[i] + seq[i + 1]);
else {
d.pb(seq[i]);
if(i + 1 < seq.size())d.pb(seq[i + 1]);
}
}
}
return -1;
};
int o = 0;
while(true) {
int flg = 1, sum = 0;
vector<pii> nr;
vector<int>().swap(d);
for(auto u : rg) {
int res = work(sum + 1, sum + u);
flg &= (res != -1);
nr.pb({res, u - res});
sum += u;
}
if(flg) {
vector<int>().swap(rg);
for(auto t : nr) {if(t.FR)rg.pb(t.FR); if(t.SE)rg.pb(t.SE);}
break;
}
// for(int i = 1; i <= n; i++)cerr << a[i] << ' '; cerr << endl;
doit(d);
}
// cerr << w << ' ' << type << endl;
// for(int i = 1; i <= n; i++)cerr << a[i] << ' '; cerr << endl;
// for(int u : rg)cerr << u << ' '; cerr << endl;
}
if(type)doit(vector<int>(n, 1));
for(int i = 1; i <= n; i++)assert(a[i] == i);
printf("%lu\n", ans.size());
for(auto t : ans) {
printf("%lu ", t.size());
for(int u : t)printf("%d ", u); putchar('\n');
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3728kb
input:
4 3 1 2 4
output:
2 3 2 1 1 3 1 2 1
result:
ok OK
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3772kb
input:
6 6 5 4 3 2 1
output:
2 1 6 6 1 1 1 1 1 1
result:
wrong answer Integer 1 violates the range [2, 6]