oj.uz

Submission #1116229

# Submission time Handle Problem Language Result Execution time Memory
1116229 2024-11-21T11:06:01 Z SalihSahin MalnaRISC (COI21_malnarisc) C++14
76.8521 / 100
 2 ms 592 KB 
#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int inf = 1e16;
const int N = 15;
const int M = 500;

vector< vector<array<int, 2> > > ans[M];
vector<int> deps(N);

void f(int l, int r, int depth){
   if(l == r) return;
   int m = (l + r)/2;
   deps[depth + 1] = max(deps[depth + 1], deps[depth] + max(m - l + 1, r - (m + 1) + 1));

   for(int i = l; i <= m; i++){
      vector<array<int, 2> > op;
      int st = i;
      for(int j = m+1; j <= r; j++){
         op.pb({st, j});
         st++;
         if(st > m) st = l;
      }

      ans[depth].pb(op);
   }

   f(l, m, depth + 1);
   f(m+1, r, depth + 1);
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);
   int n;
   cin>>n;

   queue<array<int, 3> > q;
   q.push({0, n-1, 0});
   while(!q.empty()){
      int l = q.front()[0], r = q.front()[1], d = q.front()[2];
      q.pop();
      if(l == r) continue;
      int m = (l + r)/2;
      deps[d + 1] = max(deps[d + 1], deps[d] + max(m - l + 1, r - (m + 1) + 1));

      for(int i = l; i <= m; i++){
         vector<array<int, 2> > op;
         int st = i;
         for(int j = m+1; j <= r; j++){
            op.pb({st, j});
            st++;
            if(st > m) st = l;
         }

         ans[deps[d] + i - l].pb(op);
      }

      q.push({l, m, d + 1});
      q.push({m+1, r, d + 1});
   }

   int cnt = 0;
   for(int i = 0; i < M; i++){
      if(!ans[i].size()) break;
      cnt++;
   }

   cout<<cnt<<endl;
   for(int i = 0; i < cnt; i++){
      for(auto itr: ans[i]){
         for(auto itr2: itr){
            cout<<"CMPSWP R"<<itr2[0]+1<<" R"<<itr2[1]+1<<" ";
         }
      }
      cout<<endl;
   }

   return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #2
8.25 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #3
8.4444444444 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #4
7.6666666667 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #5
7.1481481481 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #6
7.213592233 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #7
7.0526315789 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #8
7.0303030303 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #9
7.0402684564 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 592 KB Partially correct

Subtask #10
7.0060240964 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 592 KB Partially correct