QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124543#5176. 多控制反转pandapythoner25 1ms3536kbC++146.5kb2023-07-15 05:20:422023-07-15 05:20:43

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-15 05:20:43]
  • 评测
  • 测评结果：25
  • 用时：1ms
  • 内存：3536kb
查看
  • [2023-07-15 05:20:42]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


#ifdef LOCAL
#define _GLIBCXX_DEBUG
bool local = true;
#else
bool local = false;
#endif


mt19937 rnd(234);
const ll inf = 1e18;


struct operation{
    int t, x, y, z;


    operation(){}
    operation(int t, int x, int y = 0, int z = 0) : t(t), x(x), y(y), z(z) {}
};


ostream& operator<<(ostream &out, operation &op){
    out << op.t << " " << op.x;
    if(op.t >= 2){
        out << " " << op.y;
    }
    if(op.t >= 3){
        out << " " << op.z;
    }
    return out;
}


int n, m, Q, subgroup;
vector<operation> rs;


void add_op(int t, int x, int y = 0, int z = 0){
    rs.emplace_back(t, x, y, z);
}


void solve_12(){
    rs.clear();
    add_op(2, 0, n + 1);
    for(int i = 1; i < n; i += 1){
        add_op(3, i, n + i, n + i + 1);
    }
    add_op(2, 2 * n, n);
    for(int i = n - 1; i >= 1; i -= 1){
        add_op(3, i, n + i, n + i + 1);
    }
    add_op(2, 0, n + 1);
}


void add_ops(vector<operation> t){
    for(auto x: t){
        rs.push_back(x);
    }
}


void add_ops_rev(vector<operation> t){
    reverse(all(t));
    for(auto x: t){
        rs.push_back(x);
    }
}


void add_ops_rev_not_last(vector<operation> t){
    t.pop_back();
    reverse(all(t));
    for(auto x: t){
        rs.push_back(x);
    }
}


int cnt_aboba = 0;


void solve(int n, vector<int> a, int dpth){
    if(n == 0){
        add_op(1, a[0]);
        cnt_aboba += 1;
        return;
    }
    if(n == 1){
        add_op(2, a[0], a[1]);
        cnt_aboba += 1;
        return;
    }
    if(n == 2){
        add_op(3, a[0], a[1], a[2]);
        cnt_aboba += 1;
        return;
    }
    int s = n / 2 + 1;
    vector<int> b(s + 2);
    for(int i = 0; i < s; i += 1){
        b[i] = a[i];
    }
    b[s] = a[n + 1];
    b[s + 1] = a[n];
    int t = n - s + 1;
    vector<int> c(t + 2);
    for(int i = 0; i < t - 1; i += 1){
        c[i] = a[n - i - 1];
    }
    c[t - 1] = a[n + 1];
    c[t] = a[n];
    c[t + 1] = a[0];
    solve(s, b, dpth + 1);
    solve(t, c, dpth + 1);
    solve(s, b, dpth + 1);
    solve(t, c, dpth + 1);
}


void get_biba(int s, vector<int> a, vector<int> b, int rs_pos, vector<operation> &rs){
    if(s == 0){
        rs.push_back(operation(1, rs_pos));
        return;
    }
    if(s == 1){
        rs.push_back(operation(2, a[0], rs_pos));
        return;
    }
    if(s == 2){
        rs.push_back(operation(3, a[0], a[1], rs_pos));
        return;
    }
    vector<operation> t;
    t.push_back(operation(3, a[0], a[1], b[0]));
    for(int i = 2; i < s - 1; i += 1){
        t.push_back(operation(3, a[i], b[i - 2], b[i - 1]));
    }
    // vector<operation> rs;
    for(auto x: t){
        rs.push_back(x);
    }
    rs.push_back(operation(3, a[s - 1], b[s - 3], rs_pos));
    reverse(all(t));
    for(auto x: t){
        rs.push_back(x);
    }
}


void solve_fuck(int n, vector<int> a){
    if(n <= 10){
        solve(n, a, 0);
        return;
    }
    int t = 2;
    while((1 << (t + 1)) < n - t){
        t += 1;
    }
    int s = n - t;
    vector<int> c;
    for(int i = s; i < n; i += 1){
        c.push_back(a[i]);
    }
    c.push_back(a[n + 1]);
    c.push_back(a[n]);
    c.push_back(a[0]);
    vector<operation> biba;
    for(int i = 0; i < t; i += 1){
        biba.push_back(operation(1, c[i]));
    }
    int l = 0;
    vector<int> usd;
    for(int i = 0; i < t; i += 1){
        int mx_sz = (int)usd.size() + 2;
        vector<int> b;
        int r = min(s, l + mx_sz);
        for(int j = l; j < r; j += 1){
            b.push_back(a[j]);
        }
        l = r;
        int sz = (int)b.size();
        get_biba(sz, b, usd, a[s + i], biba);
        for(auto x: b){
            usd.push_back(x);
        }
    }
    auto rbiba = biba;
    reverse(all(rbiba));
    /*
    vector<operation> aboba;
    aboba.push_back(operation(2, a[s], a[n + 1]));
    for(auto x: biba){
        tmp.push_back(x);
    }
    for(auto x: aboba){
        tmp.push_back(x);
    }
    reverse(all(biba));
    for(auto x: biba){
        tmp.push_back(x);
    }
    for(int i = 0; i < t; i += 1){
        tmp.push_back(operation(1, c[i]));
    }
    */

    vector<int> d(t + 2);
    for(int i = 0; i < t; i += 1){
        d[i] = a[s + i];
    }

    d[t] = a[n + 1];
    d[t + 1] = a[0];

    for(auto x: biba){
        rs.push_back(x);
    }
    solve(t, d, 0);
    for(auto x: rbiba){
        rs.push_back(x);
    }    

    /*
    for(auto x: tmp){
        rs.push_back(x);
    }
    */
    solve(t + 1, c, 0);


    for(auto x: biba){
        rs.push_back(x);
    }
    solve(t, d, 0);
    for(auto x: rbiba){
        rs.push_back(x);
    }   
    /*
    for(auto x: tmp){
        rs.push_back(x);
    }
    */

    solve(t + 1, c, 0);
}


void solve(){
    rs.clear();
    vector<int> a(m);
    for(int i = 0; i < m; i += 1){
        a[i] = i;
    }
    // shuffle(all(a), rnd);
    cnt_aboba = 0;
    solve_fuck(n, a);
}


vector<int> make_operations(vector<int> t){
    for(auto op: rs){
        if(op.t == 1){
            t[op.x] ^= 1;
        } else if(op.t == 2 && t[op.x]){
            t[op.y] ^= 1;
        } else if(op.t == 3 && t[op.x] && t[op.y]){
            t[op.z] ^= 1;
        }
    }
    return t;
}


int32_t main(){
    if(!local){
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
    }
    int t = 1;
    if(local){
        t = 1000;
    }
    while(t--){
        cin >> n >> m >> Q >> subgroup;
        vector<int> t(m);
        if(0){
            for(int i = 0; i < m; i += 1){
                cin >> t[i];
            }
        }
        if(n == 0){
            rs.clear();
            add_op(1, 0);
        } else if(subgroup == 1 || subgroup == 2){
            solve_12();
        } else{
            solve();
        }
        cout << rs.size() << "\n";
        for(auto x: rs){
            cout << x << "\n";
        }
        if(local){
            cout << (flt)(rs.size()) / (flt)(n) << "\n";
        }
        if(0){
            auto nt = make_operations(t);
            for(int i = 0; i < m; i += 1){
                cout << nt[i] << " ";
            }
            cout << "\n";
        }
    }
    return 0;
}



/*
2 6 100 1
0 1 1 0 0 0


*/
源文件, 语言: C++14

详细

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 1ms
memory: 3492kb

input:

0 2 1 1

output:

1
1 0

result:

ok OK.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

13 28 105 1

output:

27
2 0 14
3 1 14 15
3 2 15 16
3 3 16 17
3 4 17 18
3 5 18 19
3 6 19 20
3 7 20 21
3 8 21 22
3 9 22 23
3 10 23 24
3 11 24 25
3 12 25 26
2 26 13
3 12 25 26
3 11 24 25
3 10 23 24
3 9 22 23
3 8 21 22
3 7 20 21
3 6 19 20
3 5 18 19
3 4 17 18
3 3 16 17
3 2 15 16
3 1 14 15
2 0 14

result:

ok OK.

Test #3:

score: 0
Accepted
time: 1ms
memory: 3476kb

input:

5 12 41 1

output:

11
2 0 6
3 1 6 7
3 2 7 8
3 3 8 9
3 4 9 10
2 10 5
3 4 9 10
3 3 8 9
3 2 7 8
3 1 6 7
2 0 6

result:

ok OK.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3484kb

input:

20 42 161 1

output:

41
2 0 21
3 1 21 22
3 2 22 23
3 3 23 24
3 4 24 25
3 5 25 26
3 6 26 27
3 7 27 28
3 8 28 29
3 9 29 30
3 10 30 31
3 11 31 32
3 12 32 33
3 13 33 34
3 14 34 35
3 15 35 36
3 16 36 37
3 17 37 38
3 18 38 39
3 19 39 40
2 40 20
3 19 39 40
3 18 38 39
3 17 37 38
3 16 36 37
3 15 35 36
3 14 34 35
3 13 33 34
3 12 ...

result:

ok OK.

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #5:

score: 10
Accepted
time: 0ms
memory: 3480kb

input:

48 98 385 2

output:

97
2 0 49
3 1 49 50
3 2 50 51
3 3 51 52
3 4 52 53
3 5 53 54
3 6 54 55
3 7 55 56
3 8 56 57
3 9 57 58
3 10 58 59
3 11 59 60
3 12 60 61
3 13 61 62
3 14 62 63
3 15 63 64
3 16 64 65
3 17 65 66
3 18 66 67
3 19 67 68
3 20 68 69
3 21 69 70
3 22 70 71
3 23 71 72
3 24 72 73
3 25 73 74
3 26 74 75
3 27 75 76
3 ...

result:

ok OK.

Test #6:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

41 84 329 2

output:

83
2 0 42
3 1 42 43
3 2 43 44
3 3 44 45
3 4 45 46
3 5 46 47
3 6 47 48
3 7 48 49
3 8 49 50
3 9 50 51
3 10 51 52
3 11 52 53
3 12 53 54
3 13 54 55
3 14 55 56
3 15 56 57
3 16 57 58
3 17 58 59
3 18 59 60
3 19 60 61
3 20 61 62
3 21 62 63
3 22 63 64
3 23 64 65
3 24 65 66
3 25 66 67
3 26 67 68
3 27 68 69
3 ...

result:

ok OK.

Test #7:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

50 102 401 2

output:

101
2 0 51
3 1 51 52
3 2 52 53
3 3 53 54
3 4 54 55
3 5 55 56
3 6 56 57
3 7 57 58
3 8 58 59
3 9 59 60
3 10 60 61
3 11 61 62
3 12 62 63
3 13 63 64
3 14 64 65
3 15 65 66
3 16 66 67
3 17 67 68
3 18 68 69
3 19 69 70
3 20 70 71
3 21 71 72
3 22 72 73
3 23 73 74
3 24 74 75
3 25 75 76
3 26 76 77
3 27 77 78
3...

result:

ok OK.

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #8:

score: 10
Accepted
time: 1ms
memory: 3428kb

input:

0 2 1 3

output:

1
1 0

result:

ok OK.

Test #9:

score: -10
Wrong Answer
time: 1ms
memory: 3500kb

input:

19 40 153 3

output:

116
1 16
1 17
1 18
3 0 1 16
3 2 3 0
3 4 0 1
3 5 1 17
3 4 0 1
3 2 3 0
3 6 7 0
3 8 0 1
3 9 1 2
3 10 2 3
3 11 3 4
3 12 4 5
3 13 5 18
3 12 4 5
3 11 3 4
3 10 2 3
3 9 1 2
3 8 0 1
3 6 7 0
3 16 17 0
3 18 0 20
3 16 17 0
3 18 0 20
3 6 7 0
3 8 0 1
3 9 1 2
3 10 2 3
3 11 3 4
3 12 4 5
3 13 5 18
3 12 4 5
3 11 3 4
...

result:

wrong answer Wrong solution.

Subtask #4:

score: 0
Wrong Answer

Test #13:

score: 10
Accepted
time: 1ms
memory: 3428kb

input:

0 2 1 4

output:

1
1 0

result:

ok OK.

Test #14:

score: -10
Wrong Answer
time: 1ms
memory: 3504kb

input:

18 20 325 4

output:

116
1 15
1 16
1 17
3 0 1 15
3 2 3 0
3 4 0 1
3 5 1 16
3 4 0 1
3 2 3 0
3 6 7 0
3 8 0 1
3 9 1 2
3 10 2 3
3 11 3 4
3 12 4 5
3 13 5 17
3 12 4 5
3 11 3 4
3 10 2 3
3 9 1 2
3 8 0 1
3 6 7 0
3 15 16 0
3 17 0 19
3 15 16 0
3 17 0 19
3 6 7 0
3 8 0 1
3 9 1 2
3 10 2 3
3 11 3 4
3 12 4 5
3 13 5 17
3 12 4 5
3 11 3 4
...

result:

wrong answer Wrong solution.

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Wrong Answer

Test #20:

score: 0
Wrong Answer
time: 1ms
memory: 3464kb

input:

14 16 393 6

output:

92
1 11
1 12
1 13
3 0 1 11
3 2 3 0
3 4 0 1
3 5 1 12
3 4 0 1
3 2 3 0
3 6 7 0
3 8 0 1
3 9 1 2
3 10 2 13
3 9 1 2
3 8 0 1
3 6 7 0
3 11 12 0
3 13 0 15
3 11 12 0
3 13 0 15
3 6 7 0
3 8 0 1
3 9 1 2
3 10 2 13
3 9 1 2
3 8 0 1
3 6 7 0
3 2 3 0
3 4 0 1
3 5 1 12
3 4 0 1
3 2 3 0
3 0 1 11
1 13
1 12
1 11
3 11 12 14
...

result:

wrong answer Wrong solution.

Subtask #7:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #3:

0%
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:47:01 | 开源项目