제출 #966815

#제출 시각아이디문제언어결과실행 시간메모리
966815YassirSalamaDNA 돌연변이 (IOI21_dna)C++17
56 / 100
120 ms33624 KiB
#include <bits/stdc++.h> using namespace std; const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; #define endl "\n" using ull=unsigned long long; using ll=long long; using pii=pair<int,int>; const int mod=1e9+7; #define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n"; template <typename T> istream& operator>>(istream& is, vector<T> &a) { copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;} #ifdef IOI void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__); #else #define dbg(...) 1337; #endif #define pb push_back #define F first #define S second #define all(v) v.begin(),v.end() const int mxn=1e5+100; vector<vector<int>> freq1,freq2; vector<int> eq; int n; map<char,int> mp; vector<vector<vector<int>>> pref; int sum(int w,int a,int b,vector<vector<int>> &pref){ if(a==0) return pref[b][w]; else return pref[b][w]-pref[a-1][w]; } int sum(int l,int r,vector<int>& pref){ if(l==0) return pref[r]; return pref[r]-pref[l-1]; } void init(string a,string b){ mp['A']=0; mp['T']=1; mp['C']=2; n=a.length(); freq1.resize(n+1,vector<int>(3,0)); freq2.resize(n+1,vector<int>(3,0)); pref.resize(n+1,vector<vector<int>>(3,vector<int>(3,0))); eq.resize(n+1,0); for(int i=0;i<n;i++){ freq1[i][mp[a[i]]]++; freq2[i][mp[b[i]]]++; if(!i) continue; for(int j=0;j<3;j++){ freq1[i][j]+=freq1[i-1][j]; freq2[i][j]+=freq2[i-1][j]; } } for(int i=0;i<n;i++){ eq[i]=(a[i]==b[i]); if(i) eq[i]+=eq[i-1]; } for(int i=0;i<n;i++){ pref[i][mp[a[i]]][mp[b[i]]]++; if(!i) continue; for(int j=0;j<3;j++){ for(int k=0;k<3;k++){ pref[i][j][k]+=pref[i-1][j][k]; } } } } int sum(int a,int b,int l,int r,vector<vector<vector<int>>> &pref){ if(l==0) return pref[r][a][b]; else return pref[r][a][b]-pref[l-1][a][b]; } int get_distance(int x,int y){ bool ok=true; for(int i=0;i<3;i++){ ok&=(sum(i,x,y,freq1)==sum(i,x,y,freq2)); } if(!ok) return -1; int rest=y-x+1; int ans=0; rest-=sum(x,y,eq); map<int,int> mp; for(int i=0;i<3;i++){ for(int j=i+1;j<3;j++){ int a=sum(i,j,x,y,pref)-mp[i]; int b=sum(j,i,x,y,pref)-mp[j]; int c=min(a,b); if(c<=0) continue; mp[i]+=c; mp[j]+=c; int k=2*c; ans+=c; rest-=2*c; } } ans+=max(0,rest-1); return ans; } #ifdef IOI signed main(){ int n,q; cin>>n>>q; string a; cin>>a; string b; cin>>b; init(a,b); while(q--){ int a,b; cin>>a>>b; int x=get_distance(a,b); cout<<x<<endl; } } #endif

컴파일 시 표준 에러 (stderr) 메시지

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:91:11: warning: unused variable 'k' [-Wunused-variable]
   91 |       int k=2*c;
      |           ^
#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...