QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#123913 | #5176. 多控制反转 | pandapythoner | 25 | 1ms | 3540kb | C++14 | 3.5kb | 2023-07-13 23:45:25 | 2023-07-13 23:45:28 |
Judging History
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, int z) : 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 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 <= 4){
for(int i = 0; i < n; i += 1){
add_op(2, a[i], a[n]);
}
if(n % 2 == 0){
add_op(1, a[n]);
}
}
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);
if(true){
solve(t, c, dpth + 1);
}
}
void solve(){
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: 0ms
memory: 3416kb
input:
0 2 1 1
output:
1 1 0
result:
ok OK.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3480kb
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: 3424kb
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: 3488kb
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: 3496kb
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: 3452kb
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: 3436kb
input:
0 2 1 3
output:
1 1 0
result:
ok OK.
Test #9:
score: -10
Wrong Answer
time: 0ms
memory: 3452kb
input:
19 40 153 3
output:
672 2 6 15 2 11 15 2 33 15 2 17 15 1 15 2 6 19 2 11 19 2 33 19 3 6 11 15 3 33 15 19 3 6 11 15 3 33 15 19 3 17 19 15 2 6 19 2 11 19 2 33 19 3 6 11 15 3 33 15 19 3 6 11 15 3 33 15 19 3 17 19 15 2 4 19 2 16 19 2 15 19 3 4 16 6 3 15 6 19 3 4 16 6 3 15 6 19 2 6 15 2 11 15 2 33 15 2 17 15 1 15 2 6 19 2 11...
result:
wrong answer Integer 672 violates the range [0, 153]
Subtask #4:
score: 0
Wrong Answer
Test #13:
score: 10
Accepted
time: 1ms
memory: 3408kb
input:
0 2 1 4
output:
1 1 0
result:
ok OK.
Test #14:
score: -10
Wrong Answer
time: 0ms
memory: 3540kb
input:
18 20 325 4
output:
560 2 6 19 2 11 19 2 9 19 2 17 19 1 19 2 6 18 2 11 18 2 9 18 3 6 11 19 3 9 19 18 3 6 11 19 3 9 19 18 3 17 18 19 2 6 18 2 11 18 2 9 18 3 6 11 19 3 9 19 18 3 6 11 19 3 9 19 18 3 17 18 19 2 4 18 2 16 18 2 19 18 3 4 16 6 3 19 6 18 3 4 16 6 3 19 6 18 2 6 19 2 11 19 2 9 19 2 17 19 1 19 2 6 18 2 11 18 2 9 ...
result:
wrong answer Integer 560 violates the range [0, 325]
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Wrong Answer
Test #20:
score: 0
Wrong Answer
time: 1ms
memory: 3488kb
input:
14 16 393 6
output:
364 2 6 13 2 11 13 2 9 13 3 6 11 15 3 9 15 13 3 6 11 15 3 9 15 13 2 3 15 2 2 15 2 13 15 3 3 2 6 3 13 6 15 3 3 2 6 3 13 6 15 2 6 13 2 11 13 2 9 13 3 6 11 15 3 9 15 13 3 6 11 15 3 9 15 13 2 3 15 2 2 15 2 13 15 3 3 2 6 3 13 6 15 3 3 2 6 3 13 6 15 2 7 13 2 10 13 2 4 13 2 15 13 1 13 2 7 6 2 10 6 2 4 6 3 ...
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%