oj.uz

답안 #209737

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
209737 2020-03-15T12:57:16 Z Nucleist Lamps (JOI19_lamps) C++14
4 / 100
 253 ms 192328 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][2][5];
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 last)
{
    ll ans=INF;
    if(index>=n)return 0; 
    if(dp[index][state][last]!=-1)return dp[index][state][last];
    if(check(on[index]))
    {
        if(last==1)ans=min(ans,solve(index+1,1,1));
        else ans=min(ans,1+solve(index+1,1,1));
    }
    if(check(noth[index]))
    {
        ans=min(ans,solve(index+1,1,2));
    }
    if(check(off[index]))
    {
        if(last==3)ans=min(ans,solve(index+1,1,3));
        else ans=min(ans,1+solve(index+1,1,3));
    }
    if(check(tog[index]))
    {
        if(last==4)ans=min(ans,solve(index+1,1,4));
        else ans=min(ans,1+solve(index+1,1,4));
    }
    if(state==1)
    {
    if(check(on1[index]))
    {
        if(last==1)ans=min(ans,1+solve(index+1,2,1));
        else ans=min(ans,2+solve(index+1,2,1));
    }
    if(check(noth1[index]))
    {
        ans=min(ans,1+solve(index+1,2,2));
    }
    if(check(off1[index]))
    {
        if(last==3)ans=min(ans,1+solve(index+1,2,3));
        else ans=min(ans,2+solve(index+1,2,3));
    }
    if(check(tog1[index]))
    {
        if(last==4)ans=min(ans,1+solve(index+1,2,4));
        else ans=min(ans,2+solve(index+1,2,4));
    }
    }
    if(state==2)
    {
      if(check(on1[index]))
    {
        if(last==1)ans=min(ans,solve(index+1,2,1));
        else ans=min(ans,1+solve(index+1,2,1));
    }
    if(check(noth1[index]))
    {
        ans=min(ans,solve(index+1,2,2));
    }
    if(check(off1[index]))
    {
        if(last==3)ans=min(ans,solve(index+1,2,3));
        else ans=min(ans,1+solve(index+1,2,3));
    }
    if(check(tog1[index]))
    {
        if(last==4)ans=min(ans,solve(index+1,2,4));
        else ans=min(ans,1+solve(index+1,2,4));
    }  
    }
    /*if(kal[index]==0)
    {
        if(kal1[index]==kal[index])
        {
            
        }
        else
        {
            
        }
    }
    else
    {
        if(kal1[index]==kal[index])
        {
        }
        else
        {
        }
    }*/
    return dp[index][state][last]=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,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:161:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
lamp.cpp: In function 'int main()':
lamp.cpp:168:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (ll i = 0; i < kal.size(); ++i)
                  ~~^~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 78712 KB Output is correct
2 Correct 47 ms 78712 KB Output is correct
3 Correct 47 ms 78712 KB Output is correct
4 Correct 49 ms 78712 KB Output is correct
5 Correct 43 ms 78712 KB Output is correct
6 Correct 45 ms 78712 KB Output is correct
7 Correct 44 ms 78712 KB Output is correct
8 Correct 53 ms 78712 KB Output is correct
9 Correct 51 ms 78712 KB Output is correct
10 Correct 52 ms 78712 KB Output is correct
11 Correct 45 ms 78712 KB Output is correct
12 Correct 49 ms 78712 KB Output is correct
13 Incorrect 48 ms 78716 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 78712 KB Output is correct
2 Correct 47 ms 78712 KB Output is correct
3 Correct 47 ms 78712 KB Output is correct
4 Correct 49 ms 78712 KB Output is correct
5 Correct 43 ms 78712 KB Output is correct
6 Correct 45 ms 78712 KB Output is correct
7 Correct 44 ms 78712 KB Output is correct
8 Correct 53 ms 78712 KB Output is correct
9 Correct 51 ms 78712 KB Output is correct
10 Correct 52 ms 78712 KB Output is correct
11 Correct 45 ms 78712 KB Output is correct
12 Correct 49 ms 78712 KB Output is correct
13 Incorrect 48 ms 78716 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 78688 KB Output is correct
2 Correct 47 ms 78732 KB Output is correct
3 Correct 44 ms 78712 KB Output is correct
4 Correct 49 ms 78712 KB Output is correct
5 Correct 55 ms 78600 KB Output is correct
6 Correct 47 ms 78616 KB Output is correct
7 Correct 253 ms 192288 KB Output is correct
8 Correct 236 ms 192304 KB Output is correct
9 Correct 231 ms 192196 KB Output is correct
10 Correct 231 ms 192200 KB Output is correct
11 Correct 220 ms 192204 KB Output is correct
12 Correct 248 ms 192328 KB Output is correct
13 Correct 227 ms 192200 KB Output is correct
14 Correct 235 ms 192288 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 78712 KB Output is correct
2 Correct 47 ms 78712 KB Output is correct
3 Correct 47 ms 78712 KB Output is correct
4 Correct 49 ms 78712 KB Output is correct
5 Correct 43 ms 78712 KB Output is correct
6 Correct 45 ms 78712 KB Output is correct
7 Correct 44 ms 78712 KB Output is correct
8 Correct 53 ms 78712 KB Output is correct
9 Correct 51 ms 78712 KB Output is correct
10 Correct 52 ms 78712 KB Output is correct
11 Correct 45 ms 78712 KB Output is correct
12 Correct 49 ms 78712 KB Output is correct
13 Incorrect 48 ms 78716 KB Output isn't correct
14 Halted 0 ms 0 KB -