QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#280023 | #7779. Swiss Stage | ucup-team135# | AC ✓ | 1ms | 3548kb | C++20 | 4.1kb | 2023-12-09 13:25:10 | 2023-12-09 13:25:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
struct S{
bool cur[4] = {}, inv[4] = {};
char first = '\0', last = '\0';
int len = 0;
void inverse() {
for (int i = 0; i < 4; ++i) swap(cur[i], inv[i]);
first = first ^ 'a' ^ 'b';
last = last ^ 'a' ^ 'b';
}
explicit S(char c): first(c), last(c), len(1) {
cur[1] = cur[2] = 1;
inv[1] = inv[2] = 1;
if (c == 'a') cur[0] = 1;
if (c == 'b') inv[0] = 1;
}
S() = default;
friend S unite(S a, S b) {
if (a.len == 0) return b;
if (b.len == 0) return a;
S res;
res.cur[0] = (a.cur[0] && b.cur[0]) || (a.cur[2] && a.last != b.first && b.cur[1]);
res.cur[1] = (a.cur[1] && b.cur[0]) || (a.cur[3] && a.last != b.first && b.cur[1]);
res.cur[2] = (a.cur[0] && b.cur[2]) || (a.cur[2] && a.last != b.first && b.cur[3]);
res.cur[3] = (a.cur[1] && b.cur[2]) || (a.cur[3] && a.last != b.first && b.cur[3]);
res.len = a.len + b.len;
res.first = a.first;
res.last = b.last;
return res;
}
};
template<typename T>
struct SegmentTree {
int n;
vector<T> data;
SegmentTree(int n2, const string& s) : n(2 << __lg(n2)), data(2 * n) {
for (int i = 0; i < n2; ++i) data[i + n] = T(s[i]);
for (int i = n - 1; i > 0; --i) data[i] = unite(data[2 * i], data[2 * i + 1]);
}
void set(int i) {
data[i += n].inverse();
for (i /= 2; i > 0; i /= 2) {
data[i] = unite(data[2 * i], data[2 * i + 1]);
}
}
T get(int l, int r) {
T lans = T(), rans = T();
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l & 1) lans = unite(lans, data[l++]);
if (r & 1) rans = unite(data[--r], rans);
}
return unite(lans, rans);
}
};
void gen(int os, string cur, vector <string> &ans) {
if (os == 0) {
ans.push_back(cur);
return;
}
for (char c = 'a'; c <= 'c'; ++c) {
auto t = cur; t += c;
gen(os-1,t,ans);
}
}
vector <string> a;
vector <string> b,c;
string ans;
map<vector<string>,bool> u[4][4];
bool can(int len, int h, vector <string> cand) {
if ((int)cand.size()<=1) {
return true;
}
if (h == 0) {
return false;
}
if(u[len][h].count(cand)) return u[len][h][cand];
for (int i = 0; i + 2 <= len; ++i) {
for (auto e : b) {
vector <vector <string>>go(3);
for (auto x : cand) {
int cnt = 0;
for (int j = 0; j < 2; ++j) {
cnt += e[j]==x[i+j];
}
go[cnt].push_back(x);
}
bool ok = 1;
for (auto v : go) {
ok &= can(len, h - 1, v);
}
if (ok) {
u[len][h][cand]=true;
return true;
}
}
}
u[len][h][cand]=false;
return false;
}
int que=0;int n;
string guess(int l, int len, int h, vector <string> cand) {
assert(!cand.empty());
if ((int)cand.size()<=1) {
return cand.front();
}
if(h==0)assert(0);
for (int i = 0; i + 2 <= len; ++i) {
for (auto e : b) {
vector <vector <string>>go(3);
for (auto x : cand) {
int cnt = 0;
for (int j = 0; j < 2; ++j) {
cnt += e[j]==x[i+j];
}
go[cnt].push_back(x);
}
bool ok = 1;
for (auto v : go) {
ok &= can(len, h - 1, v);
}
if (ok) {
cout << "? " << l + i + 1 << ' ' << e << endl;++que;assert(que<=(4*n+2)/3);
int ans; cin >> ans;
return guess(l, len, h - 1, go[ans]);
}
}
}
assert(0);
}
int f[3][3];
int32_t main() {
int x,y;cin>>x>>y;
int res=0;
while(x<3)
{
res+=(1+1*(x==2 || y==2));
++x;
}
cout<<res;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
0 1
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
1 2
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
0 0
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
0 2
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3384kb
input:
1 0
output:
3
result:
ok 1 number(s): "3"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
1 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
2 0
output:
2
result:
ok 1 number(s): "2"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3432kb
input:
2 1
output:
2
result:
ok 1 number(s): "2"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
2 2
output:
2
result:
ok 1 number(s): "2"
Extra Test:
score: 0
Extra Test Passed