結果
| 問題 |
No.1437 01 Sort
|
| ユーザー |
 lmxyue
|
| 提出日時 | 2025-08-25 16:12:52 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 75 ms / 2,000 ms |
| コード長 | 7,513 bytes |
| コンパイル時間 | 2,219 ms |
| コンパイル使用メモリ | 155,376 KB |
| 実行使用メモリ | 9,184 KB |
| 最終ジャッジ日時 | 2025-08-25 16:12:56 |
| 合計ジャッジ時間 | 4,232 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define all(a) a.begin(), a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define range(i, a, b) for (ll i = (a); i < (b); i++)
#define pb push_back
#define debug(x) cerr << __LINE__ << ' ' << #x << ':' << (x) << '\n'
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
template<class T> using pri_s = priority_queue<T, vector<T>, greater<T>>;
template<class T> using pri_b = priority_queue<T>;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr int mod1e9 = 1000000007;
constexpr int mod998 = 998244353;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
constexpr ll ten(int n) { return n ? 10 * ten(n - 1) : 1; };
int dx[] = { 1,0,-1,0,1,1,-1,-1 }; int dy[] = { 0,1,0,-1,1,-1,1,-1 };
ll mul(ll a, ll b) { return (a > INF / b ? INF : a * b); }
void fail() { cout << "-1\n"; exit(0); } void no() { cout << "No\n"; exit(0); }
template<class T> void er(T a) { cout << a << '\n'; exit(0); }
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }
template<class T> istream &operator >> (istream &s, vector<T> &v) { for (auto &e : v) s >> e; return s; }
template<class T> ostream &operator << (ostream &s, const vector<T> &v) { for (auto &e : v) s << e << ' '; return s; }
template<class T, class U> ostream &operator << (ostream &s, const pair<T, U> &p) { s << p.first << ' ' << p.second; return s; }
struct fastio {
fastio() {
cin.tie(0); cout.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(20);
cerr << fixed << setprecision(20);
}
}fastio_;
template<class T> class segtree {
int n;
vector<T> data;
T id = 0;
T operation(T a, T b) { return a + b; };
public:
segtree(int _n) {
n = 1;
while (n < _n + 2) n <<= 1;
data = vector<T>(2 * n, id);
}
segtree(vector<T> vec) {
int _n = vec.size();
n = 1;
while (n < _n + 2) n <<= 1;
data = vector<T>(2 * n, id);
for (int i = 0; i < _n; i++) data[i + n] = vec[i];
for (int i = n - 1; i >= 1; i--) data[i] = operation(data[i << 1], data[i << 1 | 1]);
}
void change(int i, T x) {
i += n;
data[i] = x;
while (i > 1) {
i >>= 1;
data[i] = operation(data[i << 1], data[i << 1 | 1]);
}
}
void add(int i, T x) { change(i, data[i + n] + x); }
T get(int a, int b) {
T left = id; T right = id;
a += n; b += n;
while (a < b) {
if (a & 1) left = operation(left, data[a++]);
if (b & 1) right = operation(data[--b], right);
a >>= 1; b >>= 1;
}
return operation(left, right);
}
T get_all() { return data[1]; }
T operator[](int i) { return data[i + n]; }
};
ll solve1(int n, string s) {
string g = s;
sort(all(g));
map<string, int> mp;
queue<string> que;
que.push(s);
mp[s] = 0;
while (!que.empty()) {
string str = que.front(); que.pop();
string a = str.back() + str.substr(0, n - 1);
string b = a;
swap(b[0], b[1]);
if (!mp.count(a)) {
mp[a] = mp[str] + 1;
que.push(a);
}
if (!mp.count(b)) {
mp[b] = mp[str] + 1;
que.push(b);
}
}
return mp[g];
}
ll solve(ll n, string s) {
assert(2 <= n && n <= ten(5));
rep(i, n) assert(s[i] == '0' || s[i] == '1');
vector<ll> one;
rep(i, n) if (s[i] == '1') one.pb(i);
ll sz = one.size();
if (sz == 0) return 0;
rep(i, sz) one.pb(one[i] + n);
vector<ll> d;
d.pb(0);
rep(i, 2 * sz - 1) d.pb(one[i + 1] - one[i] - 1);
rep(i, 2 * sz - 1) d[i + 1] += d[i];
segtree<ll> seg(2 * n);
rep(i, sz) seg.add(d[i], 1);
vector<bool> check(sz);
rep(i, sz) check[i] = (sz - i + one[i] == n);
ll ans = INF;
rep(i, sz) {
ll res = 0;
if (s[0] == '1' && s[n - 1] == '1' && check[i]) {
int f = 1;
ll ok = n, ng = 1;
while (ok - ng > 1) {
ll mid = (ok + ng) / 2;
ll r = mid - 1 + d[i];
ll g = seg.get(r + 1, 2 * n);
if (d[sz - 1] - d[i] <= mid - 1 && g != 0) g++;
if (g <= mid) ok = mid;
else ng = mid;
}
{
ll r = d[i];
ll g = seg.get(r + 1, 2 * n);
if (d[sz - 1] - d[i] <= 0 && g != 0) g++;
if (chmin(ok, g)) f = 0;
}
res = ok * n;
res -= one[i];
res += n - sz - ok;
res += f;
//debug(res);
//debug(ok);
}
else {
ll ok = n, ng = -1;
while (ok - ng > 1) {
ll mid = (ok + ng) / 2;
ll r = mid + d[i];
ll g = seg.get(r + 1, 2 * n);
if (d[sz - 1] - d[i] <= mid && g != 0) {
g++;
if (s[0] == '1' && s[n - 1] == '0' && g != 0 && d[sz] - d[i] > mid) g--;
}
if (g <= mid) ok = mid;
else ng = mid;
}
res = ok * n;
res -= one[i];
res += n - sz - ok;
//debug(res);
//debug(ok);
}
//debug(res);
if (res < 0) res += n;
chmin(ans, res);
seg.add(d[i], -1);
seg.add(d[i + sz], 1);
}
return ans;
}
int main() {
int n;
cin >> n;
string s;
cin >> s;
cout << solve(n, s) << '\n';
}