QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#280023#7779. Swiss Stageucup-team135#AC ✓1ms3548kbC++204.1kb2023-12-09 13:25:102023-12-09 13:25:11

Judging History

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

  • [2023-12-09 13:25:11]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3548kb
  • [2023-12-09 13:25:10]
  • 提交

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