QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #618524 | #8. 奇数国 | ucup-team4906 | 0 | 0ms | 30128kb | C++17 | 3.7kb | 2024-10-06 23:12:23 | 2024-10-06 23:12:24 |
Judging History
answer
//by 72
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
// #define int long long
using namespace std;
const int mod = 998244353;
const int N = 1e6 + 10;
const int M = 1e4 + 10;
// const int inf = 1e18;
typedef array<int, 3> a3;
typedef long long ll;
int n, m, f[N], sz1[N], sz2[N], rt[N], qsy[N];
pii a[N];
int find(int x) {return x == f[x] ? x : find(f[x]);}
int s[N], tot = 0;
// 扩展域并查集
bool merge(int x, int y) {
int p = find(x), q = find(y);
if(p == q) return false;
if(sz1[p] + sz2[p] < sz1[q] + sz2[q]) swap(p, q);
f[q] = p, rt[q] = 0;
sz1[p] += sz1[q], sz2[p] += sz2[q];
s[++ tot] = q;
return true;
}
void del(){//删除栈顶边
if(! tot) return;
int y = s[tot --]; sz1[f[y]] -= sz1[y], sz2[f[y]] -= sz2[y];
f[y] = y, rt[y] = 1;
}
int cnt[N];
int dp[M][M / 2], pre[M][M / 2];
pii now[N];
void sol() {
cin >> n >> m;
F(i, 1, 4 * n) {
f[i] = i, rt[i] = 1;
if(i <= 2 * n) sz1[i] = 1, sz2[i] = 0;
else sz2[i] = 1, sz1[i] = 0;
}
F(i, 1, m) cin >> a[i].fi >> a[i].se;
Fd(i, m, 1) {
auto [u, v] = a[i];
if(find(u) == find(v)) continue;
int sum = 0, qsyy = tot;
if(! merge(u, v + 2 * n)) continue;
merge(v, u + 2 * n);
int mx = 0;
F(j, 1, 4 * n) if(rt[j]) {
// 保证每个连通块会被遍历两次，两次中的集合互为反点
int x = sz1[j], y = sz2[j];
if(x > y) swap(x, y);
mx = max(mx, y - x);
sum += x, cnt[y - x] ++;
}
sum /= 2;
// vector<pii> now;
int idx = 0;
F(j, 1, mx) if(cnt[j]) now[++ idx] = {j, cnt[j] / 2}, cnt[j] = 0;
sum = n - sum; // 背出这么多
bitset<5001> g;
g[0] = 1;
F(j, 1, idx) {
auto [x, y] = now[j];
if(g[sum]) break;
for(int j = 0, now; y; j ++) {
now = min(1 << j, y), y -= now;
g |= g << (now * x);
}
}
if(! g[sum]) {
while(tot != qsyy) del();
}
}
// 对于每一个连通块标记 0 表示里面的 <= 2 * n 为 0 反之为 1
vector<a3> tmp;
// F(i, 1, 4 * n) cout << i << " " << find(i) << "!\n";
F(i, 1, 4 * n) if(rt[i]) {
tmp.push_back({i, sz1[i], sz2[i]});
rt[find(i + 2 * n)] = 0; // 保留这个集合 把另一个删了
}
dp[0][0] = 1;
assert(tmp.size() < M);
for(int i = 0; i < tmp.size(); i ++) {
auto [id, x, y] = tmp[i];
F(j, 0, n) if(dp[i][j]) {
if(j + x <= n) dp[i + 1][j + x] = 1, pre[i + 1][j + x] = j;
if(j + y <= n) dp[i + 1][j + y] = 1, pre[i + 1][j + y] = j;
}
}
int now = n;
Fd(i, tmp.size(), 1) {
auto [id, x, y] = tmp[i - 1];
// cout << id << " " << x << " " << y << "!\n";
int qaq = now - pre[i][now];
now = pre[i][now];
if(qaq == y) qsy[id] = 1;
// cout << now << "??\n";
// 0 代表小于等于2*n的选0
}
vector<int> res(2 * n + 1);
F(i, 1, 4 * n) if(rt[find(i)]) {
// cout << i << "??\n";
int flag = qsy[find(i)];
// cout << flag << "!!\n";
if(i <= 2 * n) res[i] = flag;
else res[i - 2 * n] = flag ^ 1;
}
F(i, 1, 2 * n) cout << res[i]; cout << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
F(i, 1, t) sol();
return 0;
}
//sldl
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 30128kb
input:
122 1 47 84606 1 39 10304 0 31 46 0 47 50 1 16 80142 1 15 55620 1 56 8487 1 22 65813 0 17 28 1 45 73139 0 41 47 1 15 73640 1 40 44390 1 68 70490 0 63 69 0 39 40 0 12 16 1 25 3444 0 25 27 1 18 31800 1 60 89056 1 60 52890 0 53 60 0 53 60 1 63 3243 1 54 9100 0 51 59 1 35 36461 1 61 52428 0 55 61 1 50 6...
output:
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
result:
wrong answer 1st lines differ - expected: '3448280', found: '000000000000000000000000000000...1111111111111111111111111111111'
Test #2:
score: 0
Runtime Error
input:
10000 1 3204 2085 0 3193 3210 0 5567 5581 0 5070 5093 1 7744 53578 0 7726 7744 1 5938 90890 0 5933 5946 1 2282 404 0 2275 2293 0 5529 5552 0 5411 5427 1 1288 83658 1 1691 75254 1 8728 1909 1 9085 92560 0 9068 9085 0 8728 8731 1 6452 52632 0 6444 6458 0 1691 1704 0 1270 1288 0 5233 5248 0 5400 5420 0...
output:
result:
Test #3:
score: 0
Runtime Error
input:
20000 0 4519 6399 0 5538 5991 0 5830 7147 1 5838 256887 0 5544 7321 1 3889 10561 1 2843 775260 0 1555 2973 0 2570 5389 0 5338 6500 1 9416 950309 1 5569 690690 1 3145 135315 1 2365 35167 1 3940 43 1 5310 5353 1 8337 568841 1 5796 169 1 3104 746130 0 2515 3432 1 10626 35611 0 8635 12588 1 10562 946774...
output:
result:
Test #4:
score: 0
Runtime Error
input:
30000 1 12080 458075 0 9890 15050 1 7144 149 0 4091 10808 1 5942 843378 0 2599 9264 1 9921 6647 0 6378 12730 1 8131 602651 0 5475 11565 1 9005 870870 0 6625 12774 1 11492 690690 0 8194 14863 1 4340 256 0 918 6863 1 7069 344488 0 3763 10001 1 12418 8192 0 9118 15941 1 11125 690690 0 8462 14279 1 9951...
output:
result:
Test #5:
score: 0
Runtime Error
input:
50000 1 29347 187726 0 25914 32532 1 20674 8192 0 15953 24784 1 24117 4752 0 19706 27975 1 22413 538 0 18457 27027 1 25177 931944 0 20749 29602 1 25822 52728 0 22542 28875 1 27405 746130 0 23587 31278 1 24494 24187 0 20318 27988 1 23628 85158 0 20006 28203 1 20524 24389 0 16166 24111 1 29127 733825 ...
output:
result:
Test #6:
score: 0
Runtime Error
input:
60000 1 6 2 1 12 3 1 18 5 1 24 7 1 30 11 1 36 13 1 42 17 1 48 19 1 54 23 1 60 29 1 66 31 1 72 37 1 78 41 1 84 43 1 90 47 1 96 53 1 102 59 1 108 61 1 114 67 1 120 71 1 126 73 1 132 79 1 138 83 1 144 89 1 150 97 1 156 101 1 162 103 1 168 107 1 174 109 1 180 113 1 186 127 1 192 131 1 198 137 1 204 139 ...
output:
result:
Test #7:
score: 0
Runtime Error
input:
70000 1 7 2 1 14 3 1 21 5 1 28 7 1 35 11 1 42 13 1 49 17 1 56 19 1 63 23 1 70 29 1 77 31 1 84 37 1 91 41 1 98 43 1 105 47 1 112 53 1 119 59 1 126 61 1 133 67 1 140 71 1 147 73 1 154 79 1 161 83 1 168 89 1 175 97 1 182 101 1 189 103 1 196 107 1 203 109 1 210 113 1 217 127 1 224 131 1 231 137 1 238 13...
output:
result:
Test #8:
score: 0
Runtime Error
input:
80000 1 8 2 1 16 3 1 24 5 1 32 7 1 40 11 1 48 13 1 56 17 1 64 19 1 72 23 1 80 29 1 88 31 1 96 37 1 104 41 1 112 43 1 120 47 1 128 53 1 136 59 1 144 61 1 152 67 1 160 71 1 168 73 1 176 79 1 184 83 1 192 89 1 200 97 1 208 101 1 216 103 1 224 107 1 232 109 1 240 113 1 248 127 1 256 131 1 264 137 1 272 ...
output:
result:
Test #9:
score: 0
Runtime Error
input:
90000 1 9 2 1 18 3 1 27 5 1 36 7 1 45 11 1 54 13 1 63 17 1 72 19 1 81 23 1 90 29 1 99 31 1 108 37 1 117 41 1 126 43 1 135 47 1 144 53 1 153 59 1 162 61 1 171 67 1 180 71 1 189 73 1 198 79 1 207 83 1 216 89 1 225 97 1 234 101 1 243 103 1 252 107 1 261 109 1 270 113 1 279 127 1 288 131 1 297 137 1 306...
output:
result:
Test #10:
score: 0
Runtime Error
input:
100000 1 10 2 1 20 3 1 30 5 1 40 7 1 50 11 1 60 13 1 70 17 1 80 19 1 90 23 1 100 29 1 110 31 1 120 37 1 130 41 1 140 43 1 150 47 1 160 53 1 170 59 1 180 61 1 190 67 1 200 71 1 210 73 1 220 79 1 230 83 1 240 89 1 250 97 1 260 101 1 270 103 1 280 107 1 290 109 1 300 113 1 310 127 1 320 131 1 330 137 1...