QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#307626#962. Thanks to MikeMirzayanovyllcmWA 1ms3772kbC++142.8kb2024-01-18 21:53:412024-01-18 21:53:42

Judging History

This is the latest submission verdict.

  • [2024-01-18 21:53:42]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3772kb
  • [2024-01-18 21:53:41]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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]