oj.uz

Submission #235406

# Submission time Handle Problem Language Result Execution time Memory
235406 2020-05-28T08:43:10 Z Charis02 Lamps (JOI19_lamps) C++14
0 / 100
 1000 ms 4984 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<unordered_map>
#include<set>
#include<algorithm>
#define ll int
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7

using namespace std;

ll n;
string s,t;
bool vis[N][2];
int steps[N][2];

void solve()
{
    rep(i,0,N)
        steps[i][0] = steps[i][1] = n;
    queue < pair < int,int > > q;
    int ss = 0;
    rep(i,0,n)
        ss += (s[i]-'0')*(1 << i);
    q.push(mp(ss,0));
    vis[ss][0]=true;
    steps[ss][0] = 0;

    while(!q.empty())
    {
        pair < int,int > top = q.front();
        int cur = top.first;
        int used = top.second;
        q.pop();

        int tmp = cur;

        rep(i,0,n)
        {
            tmp = cur;
            rep(j,i,n)
            {
                tmp |= (1 << j);
                if(!vis[tmp])
                {
                    vis[tmp][1]=true;
                    steps[tmp][1]=steps[cur][1]+1;
                    q.push(mp(tmp,1));
                }
            }
        }
        rep(i,0,n)
        {
            tmp = cur;
            rep(j,i,n)
            {
                tmp &= ~(1 << j);
                if(!vis[tmp][1])
                {
                    vis[tmp][1]=true;
                    steps[tmp][1]=steps[cur][1]+1;
                    q.push(mp(tmp,1));
                }
            }
        }

        if(used == 0)
        {
            rep(i,0,n)
            {
                tmp = cur;
                rep(j,i,n)
                {
                    tmp ^= (1 << j);
                    if(!vis[tmp][0])
                    {
                        vis[tmp][0]=true;
                        steps[tmp][0]=steps[cur][0]+1;
                        q.push(mp(tmp,0));
                    }
                }
            }
        }
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    cin >> s;
    cin >> t;

    solve();
    int tt=0;
    rep(i,0,n)
        tt += (t[i]-'0')*(1<<i);
    cout << min(steps[tt][0],steps[tt][1]);

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 194 ms 4856 KB Output is correct
9 Correct 205 ms 4984 KB Output is correct
10 Correct 92 ms 3832 KB Output is correct
11 Correct 89 ms 3832 KB Output is correct
12 Correct 196 ms 4856 KB Output is correct
13 Incorrect 89 ms 3968 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 194 ms 4856 KB Output is correct
9 Correct 205 ms 4984 KB Output is correct
10 Correct 92 ms 3832 KB Output is correct
11 Correct 89 ms 3832 KB Output is correct
12 Correct 196 ms 4856 KB Output is correct
13 Incorrect 89 ms 3968 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Execution timed out 1084 ms 4820 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Correct 6 ms 2688 KB Output is correct
3 Correct 6 ms 2688 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct
6 Correct 6 ms 2688 KB Output is correct
7 Correct 6 ms 2688 KB Output is correct
8 Correct 194 ms 4856 KB Output is correct
9 Correct 205 ms 4984 KB Output is correct
10 Correct 92 ms 3832 KB Output is correct
11 Correct 89 ms 3832 KB Output is correct
12 Correct 196 ms 4856 KB Output is correct
13 Incorrect 89 ms 3968 KB Output isn't correct
14 Halted 0 ms 0 KB -