提出 #577768

---

ソースコード 拡げる

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

string to_string1(ll i){
  stringstream ss;
  ss << i;
  return ss.str();
}

string toString(ll v,int keta) {
  stringstream ss;
  ss << v;
  string ret;
  ss >> ret;
  if( (int)ret.size() < keta ) {
    string tmp = "";
    rep(i,keta-(int)ret.size()) tmp += "0";
    tmp += ret;
    ret = tmp;
  }
  return ret;
}

void setter(string &s,int prefix){
  string pres = to_string1(prefix);
  rep(i,(int)pres.size()) s[i] = pres[i];
}

bool used2[11];
bool isValid(string s){
  memset(used2,false,sizeof(used2));
  rep(i,(int)s.size()) {
    if( used2[s[i]-'0'] ) return false;
    used2[s[i]-'0'] = true;
  }
  return true;
}


bool used[11];
int N;
ll pow10_;
string compute(string s){
  string ans = "";
  memset(used,false,sizeof(used));
  rep(i,(int)s.size()) {
    if( !used[s[i]-'0'] ) {
      used[s[i]-'0'] = true;
      ans += string(1,s[i]);
    } else {
      int prefix = (atoi)(s.substr(0,i+1).c_str());
      int L = prefix, R = prefix;

      int which = -1;
      while(1) {
	string tmp = s;
	--L;
	if( L < 0 ) {
	  L = pow10_ - 1;
	}
	setter(tmp,L); 
	if( isValid(to_string1(L)) ) {
	  which = 1;
	  ans = to_string1(L);
	  ans = string(i-(int)ans.size()+1,'0') + ans;
	  memset(used,false,sizeof(used));
	  rep(j,(int)ans.size()) used[ans[j]-'0'] = true;
	  break;
	}
	

	++R;	
	if( R >= pow10_ ) {
	  R = 0;
	}
	tmp = s;
	setter(tmp,R);
	if( isValid(to_string1(R)) ) {
	  which = 0;
	  ans = to_string1(R);
	  ans = string(i-(int)ans.size()+1,'0') + ans;
	  memset(used,false,sizeof(used));
	  rep(j,(int)ans.size()) used[ans[j]-'0'] = true;
	  break;
	}

      }
      assert( which != -1 );
      if( which == 1 ) { // max
	int cur = 9;
	while( (int)ans.size() < N ) {
	  if( used[cur] ) { --cur; continue; }
	  used[cur] = true;
	  ans += string(1,(char)(cur+'0'));
	  --cur;
	}
      } else { // min
      	int cur = 0;
	while( (int)ans.size() < N ) {
	  if( used[cur] ) { ++cur; continue; }
	  used[cur] = true;
	  ans += string(1,(char)(cur+'0'));
	  ++cur;
	}
      }
      break;
    }
  }
  return ans;
}


ll getDiffer(string olds,string news) {
  ll o = (atoll)(olds.c_str());
  ll n = (atoll)(news.c_str());
  return min(llabs(o-n),pow10_-llabs(o-n));
}


bool is(int i,int keta){
  memset(used,false,sizeof(used));
  string s = to_string1(i);
  s = string(keta-(int)s.size(),'0') + s;
  rep(i,(int)s.size()) {
    if( used[s[i]-'0'] ) return false;
    used[s[i]-'0'] = true;
  }
  return true;
}

string bf(string s){
 ll answ = -1;
  ll maxi = -1; 
  rep(i,(int)pow10_){
    if(!is(i,(int)s.size())) continue;
    ll v = getDiffer(s,to_string1(i));
    //cout << i <<" -> " << v << endl;
    if( maxi  == -1) {
      maxi = v;
      answ = (ll)i;
    } else if( maxi <= v ) {
      if( maxi == v ) {
	if( answ > i ) answ= i;
      } else {
	answ = i;
      }
      maxi = v;
    }
  }
  return to_string1(answ);
}

int main(){
  



  string s;
  cin >> s;


  /*

  ll answ = -1;
  ll maxi = -1; 
  rep(i,10000){
    if( !is(i)) continue;
    ll v = getDiff(s,to_string(i));
    //cout << v << endl;
    if( maxi  == -1) {
      maxi = v;
      answ = v;
    } else if( maxi <= v ) {
      maxi = v;
      cout << "!" <<i << endl;
      if( answ > i ) answ = i;
    }
  }
  cout << answ << endl;
  return 0;
*/
  string o = s;
  ll v = (atoll)(s.c_str());
  N = (int)s.size() ;
  pow10_ = 1;
  rep(i,N) pow10_ *= 10LL;
  ll five = 1;
  rep(i,N) five *= 10LL;
  five /= 2LL;
  v += five;
  v %= pow10_;
  
  //cout <<"bf =" << bf(s) << endl;
  //cout << "v = " << v << endl;
  string sv = toString(v,N);
  string  ans = "";
  ll diff = getDiffer(o,sv);

  string tmp = compute(sv);
  ll diff_tmp = getDiffer(o,sv);
  if( diff <= diff_tmp ) {
    if( ans.empty() ) {
      ans = tmp;
    } else {
      if( diff == diff_tmp ) {
	if( (atoll)(ans.c_str()) > (atoll)(tmp.c_str()) ) {
	  ans = tmp;
	}
      } else {
	ans = tmp;
      }
    }

    diff = diff_tmp;
    //cout << "diff = " << diff_tmp << endl;
  }

    //cout << string(1,'z') << endl;
  cout << ans << endl;
  return 0;
}

提出情報

ジャッジ結果