fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MAXN 300010 
  3. #define fr(i,n) for(int i=0; i<n; ++i)
  4. using namespace std;
  5.  
  6. string s[MAXN], b[MAXN], ans[MAXN];
  7. string sol;
  8. int n,m,p, mini=MAXN+10;
  9. bitset<MAXN> taj;
  10.  
  11. //this is main function which solves on basis of using pat string 
  12. //logic of implementation is same as editorial at "https://c...content-available-to-author-only...s.com/blog/entry/64331"
  13. void solve(string& pat,bool f){
  14.  
  15.     bitset<MAXN> te; //for storing which pat caused optimal soln reversed of pat or same as pat 1 for reversed
  16.     int br=0;
  17.     fr(i,n){
  18.         int br1=0, br2=0;
  19.         fr(j,m){
  20.             br1 += (s[i][j] != pat[((i&1)*2 + (j&1))]); //CACACA..
  21.             br2 += (s[i][j] != pat[((i&1)*2 + (j&1)^1)]); //ACACAC..
  22.         }
  23.         if(br2 < br1) te[i]=1;
  24.         br += min(br1,br2);
  25.     }
  26.  
  27.     if(br<mini){
  28.         //i found another optimal solution so update :
  29.         mini=br; //cost
  30.         sol=pat; //pattern
  31.         taj=te; //which one rev or normal ACACA.. or CACA.. for string pat passed as parameter
  32.         p=f; //what was status of matrix rotated or not for this optimal one 
  33.     }
  34. }
  35.  
  36. //generate all pattern of string ACGT and call solve for each string
  37. void solvepart(bool f){
  38.     //this string must lexicographicaly first in sorted order
  39.     //you can't use pat=AGCT , GCAT becoz next_permutation works by sorting 
  40.     //this pattern and then next in lexicographically increasing order
  41.     string pat="ACGT";
  42.     int i=0;
  43.     do{
  44.         //cout<<pat<<endl;
  45.         solve(pat,f);
  46.     }while(next_permutation(pat.begin(),pat.end()));
  47.     //cout<<i<<endl;
  48. }
  49.  
  50. //matrix is n * m
  51. //this function rotates matrix as well as sets proper values of n,m values
  52. void rotatematrix(string (&a)[MAXN]){
  53.     fr(i,m) b[i].clear();
  54.     fr(i,m) fr(j,n) b[i] += a[j][i];
  55.     swap(n,m);
  56.  
  57.     fr(i,n) a[i]=b[i];
  58. }
  59.  
  60. int main() {
  61. 	cin>>n>>m;
  62. 	fr(i,n) cin>>s[i];
  63. 	p=0;
  64.  
  65. 	solvepart(0);
  66. 	rotatematrix(s);
  67. 	solvepart(1);
  68.  
  69. 	// if the original matrix gives optimal solution
  70.     // re-swap n,m as they are swapped by rotatematrix(s) called before solvepart(1);
  71. 	if(!p) swap(n,m);
  72.  
  73. 	fr(i,n){
  74. 	    fr(j,m){ 
  75. 	        ans[i] += sol[(i&1)*2 + (j&1)^taj[i]];
  76. 	    }
  77. 	}
  78.  
  79. 	//if rotated matrix gave optimal solution, rotate ans matrix too
  80. 	if(p) rotatematrix(ans);
  81.  
  82. 	fr(i,n) cout<<ans[i]<<endl;
  83.  
  84. 	return 0;
  85. }
  86.  
Success #stdin #stdout 0s 43400KB
comments (?)
stdin
copy 
3 5
AGCAG
AGCAG
AGCAG
stdout
copy 
AGCGA
CTATC
AGCGA
https://ideone.com/Ypsk8P
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!