fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  3. #define ll long long int
  4. using namespace std;
  5. const int N = 1e6 + 5;
  6. const ll inf = -1e18;
  7. const int MOD = 1e9 + 7;
  8.  
  9. ll n, ans, cur, pos = -1;
  10. string s, t;
  11. std::vector<ll> v;
  12. ll querry(ll x, ll y){
  13. 	ll ct = 0;
  14. 	swap(s[x], s[y]);
  15. 	for(int i = 0; i < n; i++){
  16. 		if(s[i] != t[i])
  17. 			break;
  18. 		ct = i + 1;
  19. 	}
  20. 	swap(s[x], s[y]);
  21. 	return ct;
  22. }
  23.  
  24. int main(){
  25.    fast;
  26.    cin >> n >> s >> t;
  27.    for(int i = 0; i < n; i++){
  28.    	if(s[i] != t[i]){
  29.    		pos = i;
  30.    		break;
  31.    	}
  32.    }
  33.    if(pos == -1){
  34.    	return cout << n, 0;
  35.    }
  36.    ans = pos;
  37.    for(int i = pos + 1; i < n; i++){
  38.    	if(s[i] == t[pos])
  39.    		v.push_back(i);
  40.    }
  41.    ll lo = -1, hi = (int)v.size(), mid;
  42.    while(hi - lo > 1){
  43.    	ll mid = hi + lo >> 1;
  44.    	cur = querry(pos, v[mid]);
  45.    	if(ans == cur)
  46.    		hi = mid;
  47.    	else{
  48.    		ans = cur;
  49.    		lo = mid;
  50.    	}
  51.    }
  52.    cout << ans;
  53.  
  54.  
  55.    return 0;
  56. }
Success #stdin #stdout 0s 4180KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0EOJTK
language:
C++14 (gcc 8.3)
created:
6 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!