oj.uz

Submission #209799

# Submission time Handle Problem Language Result Execution time Memory
209799 2020-03-15T14:35:14 Z Nucleist Lamps (JOI19_lamps) C++14
4 / 100
 156 ms 158928 KB 
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
string kal,kal1;
ll n;
ll dp[1000001][8];
ll on[1000001],off[1000001],tog[1000001],noth[1000001];
ll on1[1000001],off1[1000001],tog1[1000001],noth1[1000001];
bool check(ll x)
{
    if(x>=0 && x<n)return true;
    return false;
}
ll solve(ll index,ll state)
{
    ll ans=INF;
    if(index>=n)return 0; 
    if(dp[index][state]!=-1)return dp[index][state];
    if(check(on[index]))
    {
        ans=min(ans,1+solve(on[index]+1,1));
    }
    if(check(noth[index]))
    {
        ans=min(ans,solve(noth[index]+1,1));
    }
    if(check(off[index]))
    {
        ans=min(ans,1+solve(off[index]+1,1));
    }
    if(check(tog[index]))
    {
        ans=min(ans,1+solve(tog[index]+1,1));
    }
    if(state==1)
    {
    if(check(on1[index]))
    {
        ans=min(ans,2+solve(on1[index]+1,2));
    }
    if(check(noth1[index]))
    {
        ans=min(ans,1+solve(noth1[index]+1,2));
    }
    if(check(off1[index]))
    {
        ans=min(ans,2+solve(off1[index]+1,2));
    }
    if(check(tog1[index]))
    {
        ans=min(ans,2+solve(tog1[index]+1,2));
    }
    }
    if(state==2)
    {
      if(check(on1[index]))
    {
        ans=min(ans,1+solve(on1[index]+1,2));
    }
    if(check(noth1[index]))
    {
        ans=min(ans,solve(noth1[index]+1,2));
    }
    if(check(off1[index]))
    {
        ans=min(ans,1+solve(off1[index]+1,2));
    }
    if(check(tog1[index]))
    {
        ans=min(ans,1+solve(tog1[index]+1,2));
    }  
    }
    /*if(kal[index]==0)
    {
        if(kal1[index]==kal[index])
        {
            
        }
        else
        {
            
        }
    }
    else
    {
        if(kal1[index]==kal[index])
        {
        }
        else
        {
        }
    }*/
    return dp[index][state]=ans;
}
ll preprocess(ll arr[])
{
  ll fin=-1;
  ll deb=-1;
  bool ka=false;
  for (ll i = 0; i < n; ++i)
  {
    if(arr[i]==0)
      {
        if(deb!=-1 && fin!=-1)
        {
            for (ll j = deb; j <= fin; ++j)
        {
            arr[j]=fin;
        }
        }
        deb=fin=-1;
        ka=false;
        arr[i]=-1;
      }
      else if(!ka)
      {
        ka=true;
        deb=fin=i;
      }
      else
      {
        fin++;
      }
  }
  if(deb!=-1)
  {
    for (ll j = deb; j <= fin; ++j)
        {
            arr[j]=fin;
        }
  }
}
int main()
{
  flash;
  cin>>n;
  cin>>kal>>kal1;
  memset(dp,-1,sizeof dp);
  for (ll i = 0; i < kal.size(); ++i)
  {
    if(kal[i]=='0')
    {
        if(kal1[i]==kal[i])
        {
            off[i]=1;
            noth[i]=1;
            tog1[i]=1;
            on1[i]=1;
        }
        else
        {
            on[i]=1;
            tog[i]=1;
            off1[i]=1;
            noth1[i]=1;
        }
    }
    else
    {
        if(kal1[i]==kal[i])
        {
            on[i]=1;
            noth[i]=1;
            tog1[i]=1;
            off1[i]=1;
        }
        else
        {
           off[i]=1;
           tog[i]=1;
           on1[i]=1;
           noth1[i]=1;
        }
    }
  }
  preprocess(off);
  preprocess(on);
  preprocess(tog);
  preprocess(noth);
  preprocess(off1);
  preprocess(on1);
  preprocess(tog1);
  preprocess(noth1);
  cout<<solve(0,1);
  return 0;
}
//code the AC sol !
// BS/queue/map

Compilation message

lamp.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
lamp.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
lamp.cpp: In function 'long long int preprocess(long long int*)':
lamp.cpp:152:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
lamp.cpp: In function 'int main()':
lamp.cpp:159:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (ll i = 0; i < kal.size(); ++i)
                  ~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62968 KB Output is correct
2 Correct 38 ms 62968 KB Output is correct
3 Correct 38 ms 63096 KB Output is correct
4 Correct 38 ms 62968 KB Output is correct
5 Correct 38 ms 62968 KB Output is correct
6 Correct 38 ms 62968 KB Output is correct
7 Correct 40 ms 62968 KB Output is correct
8 Correct 38 ms 62968 KB Output is correct
9 Correct 38 ms 62972 KB Output is correct
10 Correct 39 ms 62968 KB Output is correct
11 Correct 38 ms 62968 KB Output is correct
12 Correct 39 ms 62968 KB Output is correct
13 Correct 39 ms 62968 KB Output is correct
14 Correct 38 ms 63056 KB Output is correct
15 Correct 38 ms 62968 KB Output is correct
16 Incorrect 37 ms 62968 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62968 KB Output is correct
2 Correct 38 ms 62968 KB Output is correct
3 Correct 38 ms 63096 KB Output is correct
4 Correct 38 ms 62968 KB Output is correct
5 Correct 38 ms 62968 KB Output is correct
6 Correct 38 ms 62968 KB Output is correct
7 Correct 40 ms 62968 KB Output is correct
8 Correct 38 ms 62968 KB Output is correct
9 Correct 38 ms 62972 KB Output is correct
10 Correct 39 ms 62968 KB Output is correct
11 Correct 38 ms 62968 KB Output is correct
12 Correct 39 ms 62968 KB Output is correct
13 Correct 39 ms 62968 KB Output is correct
14 Correct 38 ms 63056 KB Output is correct
15 Correct 38 ms 62968 KB Output is correct
16 Incorrect 37 ms 62968 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 62968 KB Output is correct
2 Correct 39 ms 62968 KB Output is correct
3 Correct 37 ms 62968 KB Output is correct
4 Correct 38 ms 62968 KB Output is correct
5 Correct 39 ms 62968 KB Output is correct
6 Correct 37 ms 62968 KB Output is correct
7 Correct 89 ms 127692 KB Output is correct
8 Correct 156 ms 158924 KB Output is correct
9 Correct 155 ms 158924 KB Output is correct
10 Correct 155 ms 158928 KB Output is correct
11 Correct 152 ms 158924 KB Output is correct
12 Correct 91 ms 127684 KB Output is correct
13 Correct 90 ms 127688 KB Output is correct
14 Correct 98 ms 128452 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62968 KB Output is correct
2 Correct 38 ms 62968 KB Output is correct
3 Correct 38 ms 63096 KB Output is correct
4 Correct 38 ms 62968 KB Output is correct
5 Correct 38 ms 62968 KB Output is correct
6 Correct 38 ms 62968 KB Output is correct
7 Correct 40 ms 62968 KB Output is correct
8 Correct 38 ms 62968 KB Output is correct
9 Correct 38 ms 62972 KB Output is correct
10 Correct 39 ms 62968 KB Output is correct
11 Correct 38 ms 62968 KB Output is correct
12 Correct 39 ms 62968 KB Output is correct
13 Correct 39 ms 62968 KB Output is correct
14 Correct 38 ms 63056 KB Output is correct
15 Correct 38 ms 62968 KB Output is correct
16 Incorrect 37 ms 62968 KB Output isn't correct
17 Halted 0 ms 0 KB -