Submission #44886

#	Time	Username	Problem	Language	Result	Execution time	Memory
44886		RayaBurong25_1	Security Gate (JOI18_security_gate)	C++17	12 / 100	5019 ms	1980 KiB

securitygate

#include <stdio.h>
#include <vector>
#define INF 1000000007
char S[305];
std::vector<int> Xpos;
std::vector<char> ChangeBit;
typedef struct node node;
struct node
{
    int v;
    int sum, sumrev;
    int mn, mnrev;
};
int N;
node Seg[1205];
int Fen[305];
int Q[305];
void up(int p, int v)
{
    p++;
    for (; p <= N; p += p&-p)
        Fen[p] += v;
}
int qu(int p)
{
    p++;
    int r = 0;
    for (; p > 0; p -= p&-p)
        r += Fen[p];
    return r;
}
int min(int a, int b)
{
    return (a < b)?a:b;
}
int max(int a, int b)
{
    return (a > b)?a:b;
}
void makeTree(int s, int e, int cell)
{
    if (s == e)
    {
        Seg[cell].v = ((S[s] == '(')?1:-1);
        Seg[cell].sum = Seg[cell].v;
        Seg[cell].sumrev = -Seg[cell].v;
        Seg[cell].mn = Seg[cell].v;
        Seg[cell].mnrev = -Seg[cell].v;
        return;
    }
    int m = (s + e)/2;
    makeTree(s, m, 2*cell + 1);
    makeTree(m + 1, e, 2*cell + 2);
    Seg[cell].sum = Seg[2*cell + 1].sum + Seg[2*cell + 2].sum;
    Seg[cell].sumrev = Seg[2*cell + 1].sumrev + Seg[2*cell + 2].sumrev;
    Seg[cell].mn = min(Seg[2*cell + 1].mn, Seg[2*cell + 1].sum + Seg[2*cell + 2].mn);
    Seg[cell].mnrev = min(Seg[2*cell + 1].mnrev, Seg[2*cell + 1].sumrev + Seg[2*cell + 2].mnrev);
}
void preprocess()
{
    int i;
    for (i = 0; i < N; i++)
    {
        up(i, ((S[i] == '(')?1:-1));
        Q[i] = qu(i);
        // printf("Q %d ", Q[i]);
    }
    makeTree(0, N - 1, 0);
}
void update(int p, int s, int e, int cell)
{
    if (s == e)
    {
        // printf("update p = %c\n", S[s]);
        Seg[cell].v = ((S[s] == '(')?1:-1);
        Seg[cell].sum = Seg[cell].v;
        Seg[cell].sumrev = -Seg[cell].v;
        Seg[cell].mn = Seg[cell].v;
        Seg[cell].mnrev = -Seg[cell].v;
        return;
    }
    int m = (s + e)/2;
    if (p <= m)
        update(p, s, m, 2*cell + 1);
    else
        update(p, m + 1, e, 2*cell + 2);
    Seg[cell].sum = Seg[2*cell + 1].sum + Seg[2*cell + 2].sum;
    Seg[cell].sumrev = Seg[2*cell + 1].sumrev + Seg[2*cell + 2].sumrev;
    Seg[cell].mn = min(Seg[2*cell + 1].mn, Seg[2*cell + 1].sum + Seg[2*cell + 2].mn);
    Seg[cell].mnrev = min(Seg[2*cell + 1].mnrev, Seg[2*cell + 1].sumrev + Seg[2*cell + 2].mnrev);
}
void change(int i)
{
    up(i, ((S[i] == '(')?2:-2));
    update(i, 0, N - 1, 0);
    for (; i < N; i++)
        Q[i] = qu(i);
    // for (i = 0; i < N; i++)
        // printf("Q %d ", Q[i]);
}
node query(int qs, int qe, int s, int e, int cell)
{
    // printf("query %d %d %d %d %d\n", qs, qe, s, e, cell);
    if (qs == s && qe == e)
        return Seg[cell];
    int m = (s + e)/2;
    node l = {INF, 0, 0, INF, INF};
    node r = {INF, 0, 0, INF, INF};
    if (qs <= m)
        l = query(qs, min(m, qe), s, m, 2*cell + 1);
    if (m + 1 <= qe)
        r = query(max(m + 1, qs), qe, m + 1, e, 2*cell + 2);
    node ret;
    ret.sum = l.sum + r.sum;
    ret.sumrev = l.sumrev + r.sumrev;
    ret.mn = min(l.mn, l.sum + r.mn);
    ret.mnrev = min(l.mnrev, l.sumrev + r.mnrev);
    // printf("l %d %d %d %d\n", l.sum, l.sumrev, l.mn, l.mnrev);
    // printf("r %d %d %d %d\n", r.sum, r.sumrev, r.mn, r.mnrev);
    // printf("ret %d %d %d %d\n", ret.sum, ret.sumrev, ret.mn, ret.mnrev);
    return ret;
}
int checkrange(int i, int j)
{
    int mn = INF;
    node p;
    if (i > 0)
    {
        p = query(0, i - 1, 0, N - 1, 0);
        mn = min(mn, p.mn);
        // printf("{%d %d %d %d %d} mn %d\n", p.v, p.sum, p.sumrev, p.mn, p.mnrev, mn);
    }
    p = query(i, j, 0, N - 1, 0);
    mn = min(mn, ((i > 0)?Q[i - 1]:0) + p.mnrev);
    // printf("{%d %d %d %d %d} mn %d\n", p.v, p.sum, p.sumrev, p.mn, p.mnrev, mn);
    if (j < N - 1)
    {
        p = query(j + 1, N - 1, 0, N - 1, 0);
        mn = min(mn, 2*((i > 0)?Q[i - 1]:0) - Q[j] + p.mn);
        // printf("{%d %d %d %d %d} mn %d\n", p.v, p.sum, p.sumrev, p.mn, p.mnrev, mn);
    }
    // printf("mn %d\n", mn);
    return (mn == 0);
}
int check()
{
    if (Q[N - 1]%2)
        return 0;
    else if (Q[N - 1] == 0 && query(0, N - 1, 0, N - 1, 0).mn == 0)
        return 1;
    int i, j, q;
    std::vector<int> V[610];
    V[N].push_back(-1);
    for (i = 0; i < N; i++)
    {
        q = Q[i] - Q[N - 1]/2;
        for (j = 0; j < V[q + N].size(); j++)
        {
            // printf("%d %d\n", V[q + N][j] + 1, i);
            if (checkrange(V[q + N][j] + 1, i))
                return 1;
        }
        V[Q[i] + N].push_back(i);
    }
    return 0;
}
void printTree(int s, int e, int cell)
{
    if (s == e)
    {
        printf("(%d %d) %d %d %d %d %d\n", s, e, Seg[cell].v, Seg[cell].sum, Seg[cell].sumrev, Seg[cell].mn, Seg[cell].mnrev);
        return;
    }
    int m = (s + e)/2;
    printTree(s, m, 2*cell + 1);
    printf("(%d %d) %d %d %d %d %d\n", s, e, Seg[cell].v, Seg[cell].sum, Seg[cell].sumrev, Seg[cell].mn, Seg[cell].mnrev);
    printTree(m + 1, e, 2*cell + 2);
}
int main()
{
    scanf("%d", &N);
    int i, X = 0;
    scanf("%s", S);
    for (i = 0; i < N; i++)
    {
        if (S[i] == 'x')
        {
            Xpos.push_back(i);
            X++;
            S[i] = '(';
        }
    }
    int j, s;
    for (i = 0; i < X; i++)
    {
        ChangeBit.push_back(i);
        s = ChangeBit.size();
        for (j = 0; j < s - 1; j++)
            ChangeBit.push_back(ChangeBit[j]);
    }
    int cnt = 0;
    // printf("%s\n", S);
    preprocess();
    // printTree(0, N - 1, 0);
    if (check())
        cnt++;
    for (i = 0; i < ChangeBit.size(); i++)
    {
        if (S[Xpos[ChangeBit[i]]] == '(')
            S[Xpos[ChangeBit[i]]] = ')';
        else
            S[Xpos[ChangeBit[i]]] = '(';
        // printf("%s\n", S);
        change(Xpos[ChangeBit[i]]);
        // printTree(0, N - 1, 0);
        if (check())
            cnt++;
    }
    printf("%d", cnt);
}

Compilation message (stderr)

securitygate.cpp: In function 'int check()':
securitygate.cpp:157:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < V[q + N].size(); j++)
                     ~~^~~~~~~~~~~~~~~~~
securitygate.cpp: In function 'int main()':
securitygate.cpp:207:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < ChangeBit.size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~
securitygate.cpp:181:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
securitygate.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S);
     ~~~~~^~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 43
• Subtask 5: 0 / 27