Submission #1104748

#TimeUsernameProblemLanguageResultExecution timeMemory
1104748ezzzayBoard (CEOI13_board)C++14
40 / 100
652 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define int long long #define pb push_back map<vector<int>,int >dist; string a,b; vector<int> has (vector<int> v){ int n=v.size(); for(int i=n-1;i>=0;i--){ if(v[i]){ v[i]=0; for(int j=i+1;j<n;j++){ v[j]=1; } break; } } return v; } vector<int> nem (vector<int> v){ int n=v.size(); bool u=1; for(int i=n-1;i>=0;i--){ if(v[i]==0){ v[i]=1; u=0; for(int j=i+1;j<n;j++){ v[j]=0; } break; } } if(u){ v.clear(); v.pb(1); for(int i=0;i<n;i++){ v.pb(0); } } return v; } int fun(vector<int>a, vector<int>b){ if(a.size()!=b.size()){ if(max(a.size(),b.size())>20)return 1e8; } reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); int x=0; for(int i=0;i<a.size();i++){ if(a[i]){ x+=(1<<i); } } int y=0; for(int i=0;i<b.size();i++){ if(b[i]){ y+=(1<<i); } } return abs(x-y); } signed main(){ cin>>a; vector<int>x={1},y={1}; int lvl=1; dist[{1}]=1; for(auto c:a){ if(c=='1'){ x.pb(0); lvl++; } else if(c=='2'){ x.pb(1); lvl++; } else if(c=='U'){ x.pop_back(); lvl--; } else if(c=='L'){ x=has(x); } else{ x=nem(x); } dist[x]=lvl; } lvl=1; cin>>a; for(auto c:a){ if(c=='1'){ y.pb(0); lvl++; } else if(c=='2'){ y.pb(1); lvl++; } else if(c=='U'){ y.pop_back(); lvl--; } else if(c=='L'){ y=has(y); } else{ y=nem(y); } dist[y]=lvl; } if(dist[y]>dist[x]){ swap(y,x); } int k=0; int p=dist[x]; while(dist[x]>dist[y]){ x.pop_back(); dist[x]= --p; k++; } int ans=k+fun(x,y); p=dist[x]; while(p>1){ x.pop_back(); y.pop_back(); p--; k+=2; // cout<<k+fun(x,y)<<endl; ans=min(ans,k+fun(x,y)); } cout<<ans; }

Compilation message (stderr)

board.cpp: In function 'long long int fun(std::vector<long long int>, std::vector<long long int>)':
board.cpp:55:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
board.cpp:61:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<b.size();i++){
      |                 ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...