oj.uz

Submission #209724

# Submission time Handle Problem Language Result Execution time Memory
209724 2020-03-15T12:29:41 Z Nucleist Lamps (JOI19_lamps) C++14
4 / 100
 154 ms 160972 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,0);
  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 36 ms 63096 KB Output is correct
2 Correct 36 ms 62968 KB Output is correct
3 Correct 37 ms 63096 KB Output is correct
4 Correct 37 ms 62968 KB Output is correct
5 Correct 36 ms 62968 KB Output is correct
6 Correct 36 ms 62844 KB Output is correct
7 Correct 36 ms 63096 KB Output is correct
8 Correct 36 ms 62968 KB Output is correct
9 Correct 36 ms 62968 KB Output is correct
10 Correct 36 ms 63028 KB Output is correct
11 Correct 36 ms 62968 KB Output is correct
12 Correct 36 ms 62968 KB Output is correct
13 Incorrect 36 ms 62968 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63096 KB Output is correct
2 Correct 36 ms 62968 KB Output is correct
3 Correct 37 ms 63096 KB Output is correct
4 Correct 37 ms 62968 KB Output is correct
5 Correct 36 ms 62968 KB Output is correct
6 Correct 36 ms 62844 KB Output is correct
7 Correct 36 ms 63096 KB Output is correct
8 Correct 36 ms 62968 KB Output is correct
9 Correct 36 ms 62968 KB Output is correct
10 Correct 36 ms 63028 KB Output is correct
11 Correct 36 ms 62968 KB Output is correct
12 Correct 36 ms 62968 KB Output is correct
13 Incorrect 36 ms 62968 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63096 KB Output is correct
2 Correct 37 ms 62980 KB Output is correct
3 Correct 36 ms 62968 KB Output is correct
4 Correct 36 ms 63020 KB Output is correct
5 Correct 38 ms 63096 KB Output is correct
6 Correct 37 ms 63096 KB Output is correct
7 Correct 91 ms 129608 KB Output is correct
8 Correct 154 ms 160960 KB Output is correct
9 Correct 152 ms 160968 KB Output is correct
10 Correct 152 ms 160972 KB Output is correct
11 Correct 154 ms 160968 KB Output is correct
12 Correct 92 ms 129604 KB Output is correct
13 Correct 91 ms 129608 KB Output is correct
14 Correct 96 ms 130380 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 63096 KB Output is correct
2 Correct 36 ms 62968 KB Output is correct
3 Correct 37 ms 63096 KB Output is correct
4 Correct 37 ms 62968 KB Output is correct
5 Correct 36 ms 62968 KB Output is correct
6 Correct 36 ms 62844 KB Output is correct
7 Correct 36 ms 63096 KB Output is correct
8 Correct 36 ms 62968 KB Output is correct
9 Correct 36 ms 62968 KB Output is correct
10 Correct 36 ms 63028 KB Output is correct
11 Correct 36 ms 62968 KB Output is correct
12 Correct 36 ms 62968 KB Output is correct
13 Incorrect 36 ms 62968 KB Output isn't correct
14 Halted 0 ms 0 KB -