QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#124038#5176. 多控制反转pandapythoner25 1ms3532kbC++144.6kb2023-07-14 04:49:222023-07-14 04:49:25

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-14 04:49:25]
  • 评测
  • 测评结果:25
  • 用时:1ms
  • 内存:3532kb
  • [2023-07-14 04:49:22]
  • 提交

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


void solve(int n, vector<int> a, int dpth){
    if(n == 0){
        add_op(1, a[0]);
        return;
    }
    if(n == 1){
        add_op(2, a[0], a[1]);
        return;
    }
    if(n == 2){
        add_op(3, a[0], a[1], a[2]);
        return;
    }
    if(n <= 5){
        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);
        return;
    }
    int s = n / 2;
    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];
    vector<operation> tmp;
    for(int i = 1; i < s; i += 1){
        tmp.push_back(operation(1, c[i]));
    }
    tmp.push_back(operation(3, b[0], b[1], c[1]));
    for(int i = 2; i < s; i += 1){
        tmp.push_back(operation(3, b[i], c[i - 1], c[i]));
    }
    tmp.push_back(operation(2, c[s - 1], b[s]));
    add_ops(tmp);
    // add_ops_rev_not_last(tmp);
    solve(t, c, dpth + 1);
    // add_ops(tmp);
    add_ops_rev(tmp);
    solve(t, c, dpth + 1);
}


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


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


*/

详细

Subtask #1:

score: 15
Accepted

Test #1:

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

input:

0 2 1 1

output:

1
1 0

result:

ok OK.

Test #2:

score: 0
Accepted
time: 0ms
memory: 3416kb

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: 3456kb

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: 3428kb

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: 1ms
memory: 3420kb

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: 3428kb

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: 0ms
memory: 3520kb

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: 3508kb

input:

0 2 1 3

output:

1
1 0

result:

ok OK.

Test #9:

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

input:

19 40 153 3

output:

238
1 17
1 16
1 15
1 14
1 13
1 12
1 11
1 10
3 0 1 17
3 2 17 16
3 3 16 15
3 4 15 14
3 5 14 13
3 6 13 12
3 7 12 11
3 8 11 10
2 10 20
1 9
1 10
1 11
1 12
3 18 17 9
3 16 9 10
3 15 10 11
3 14 11 12
2 12 0
1 13
1 12
3 20 9 13
3 10 13 12
2 12 18
3 0 13 19
3 12 19 20
3 0 13 19
3 12 19 20
3 18 11 0
3 20 0 19
...

result:

wrong answer Integer 238 violates the range [0, 153]

Subtask #4:

score: 0
Wrong Answer

Test #13:

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

input:

0 2 1 4

output:

1
1 0

result:

ok OK.

Test #14:

score: -10
Wrong Answer
time: 0ms
memory: 3456kb

input:

18 20 325 4

output:

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

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: 3468kb

input:

14 16 393 6

output:

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

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%