oj.uz

Submission #681774

# Submission time Handle Problem Language Result Execution time Memory
681774 2023-01-14T09:21:34 Z Cross_Ratio MalnaRISC (COI21_malnarisc) C++14
76.8521 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
int T[105];
int _N[11] = {8, 13, 16, 32, 53, 64, 73, 82, 91, 100};
int _t2[11] = {12, 22, 28, 60, 102, 124, 142, 160, 178, 196};
int _t3[11] = {6, 10, 10, 15, 21, 21, 28, 28, 29, 30};
vector<array<int, 2>> Query[155];
int DnC(vector<int> V) {
    if(V.size()<=1) return 0;
    int sz = V.size();
    int k = (sz+1) / 2;
    vector<int> V1, V2;
    int i, j;
    for(i=0;i<k;i++) V1.push_back(V[i]);
    for(i=k;i<sz;i++) V2.push_back(V[i]);
    int val = max(DnC(V1), DnC(V2));
    int s1 = V1.size(), s2 = V2.size();
    for(i=0;i<s1;i++) {
        for(j=0;j<s1;j++) {
            int k = j - i;
            if(0<=k&&k<s2) Query[val + i + 1].push_back({V1[j], V2[k]});
        }
    }
    return val + s1;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    T[1] = 0, T[2] = 1, T[3] = 3;
    int i, j;
    for(i=4;i<=100;i++) {
        T[i] = 1e9;
        for(j=1;j<=i-1;j++) {
            T[i] = min(T[i], max(T[j], T[i-j]) + max(j, i-j));
        }
        //cout << i << " : " << T[i] << '\n';
    }
    long double point = 0;
    for(i=0;i<10;i++) {
        long double k = 3 + (long double)7 * (_t2[i] - T[_N[i]] + 1) / (_t2[i] - _t3[i]);
        point += k;
    }
    //cout << point << '\n';
    vector<int>V;
    int N;
    cin >> N;
    for(i=1;i<=N;i++) V.push_back(i);
    int val = DnC(V);
    //cout << val << ' ' << T[N] << '\n';
    cout << val << '\n';
    for(i=1;i<=val;i++) {
        for(auto it : Query[i]) cout << "CMPSWP R" << it[0] << " R" << it[1] << ' ';
        cout << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
8.25 / 10.0

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

Subtask #3
8.4444444444 / 10.0

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

Subtask #4
7.6666666667 / 10.0

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

Subtask #5
7.1481481481 / 10.0

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

Subtask #6
7.213592233 / 10.0

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

Subtask #7
7.0526315789 / 10.0

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

Subtask #8
7.0303030303 / 10.0

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

Subtask #9
7.0402684564 / 10.0

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

Subtask #10
7.0060240964 / 10.0

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