結果
| 問題 | No.1830 Balanced Majority |
| ユーザー |
 milkcoffee
|
| 提出日時 | 2022-02-04 21:53:57 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,082 bytes |
| コンパイル時間 | 4,740 ms |
| コンパイル使用メモリ | 242,672 KB |
| 実行使用メモリ | 41,464 KB |
| 最終ジャッジ日時 | 2024-06-11 11:46:27 |
| 合計ジャッジ時間 | 10,457 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 24 |
ソースコード
#include <bits/stdc++.h>#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endifusing namespace std;#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define ll long long#define forin(in, n) \for (ll i = 0; i < n; i++) \cin >> in[i]#define forout(out) \for (ll i = 0; i < (ll)out.size(); i++) \cout << out[i] << endl#define rep(i, n) for (ll i = 0; i < n; ++i)#define rep_up(i, a, n) for (ll i = a; i < n; ++i)#define rep_down(i, a, n) for (ll i = a; i >= n; --i)#define P pair<ll, ll>#define pb push_back#define endl "\n"#define all(v) v.begin(), v.end()#define fi first#define se second#define vvvvll vector< vector <vector <vector<ll> > > >#define vvvll vector< vector< vector<ll> > >#define vvll vector< vector<ll> >#define vll vector<ll>#define pqll priority_queue<ll>#define pqllg priority_queue<ll, vector<ll>, greater<ll>>template<class T> inline void vin(vector<T>& v) { rep(i, v.size()) cin >> v.at(i); }template <class T>using V = vector<T>;constexpr ll INF = (1ll << 60);//constexpr ll mod = 1000000007;constexpr ll mod = 998244353;constexpr double pi = 3.14159265358979323846;template <typename T>inline bool chmax(T &a, T b){if (a < b){a = b;return 1;}return 0;}template <typename T>inline bool chmin(T &a, T b){if (a > b){a = b;return 1;}return 0;}template <typename T>void pt(T val){cout << val << "\n";}template <typename T>void pt_vll(vector<T> &v){ll vs = v.size();rep(i, vs){cout << v[i];if (i == vs - 1)cout << "\n";elsecout << " ";}}ll mypow(ll a, ll n){ll ret = 1;if (n == 0)return 1;if (a == 0)return 0;rep(i, n){if (ret > (ll)(9e18 + 10) / a)return -1;ret *= a;}return ret;}long long modpow(long long a, long long n, long long mod){long long res = 1;while (n > 0){if (n & 1)res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}long long modinv(long long a, long long m){long long b = m, u = 1, v = 0;while (b){long long t = a / b;a -= t * b;swap(a, b);u -= t * v;swap(u, v);}u %= m;if (u < 0)u += m;return u;}struct mint {ll x;constexpr mint(ll x = 0) noexcept : x((x % mod + mod) % mod) {}constexpr mint& operator+=(const mint& a) noexcept {if ((x += a.x) >= mod) x -= mod;return *this;}constexpr mint& operator-=(const mint& a) noexcept {if ((x += mod - a.x) >= mod) x -= mod;return *this;}constexpr mint& operator*=(const mint& a) noexcept { (x *= a.x) %= mod; return *this; }constexpr mint& operator/=(const mint& a) noexcept { return *this *= a.inv(); }constexpr mint operator-() const noexcept { return mint(-x); }constexpr mint operator+(const mint& a) const noexcept { return mint(*this) += a; }constexpr mint operator-(const mint& a) const noexcept { return mint(*this) -= a; }constexpr mint operator*(const mint& a) const noexcept { return mint(*this) *= a; }constexpr mint operator/(const mint& a) const noexcept { return mint(*this) /= a; }constexpr bool operator==(const mint& a) const noexcept { return x == a.x; }constexpr bool operator!=(const mint& a) const noexcept { return x != a.x; }constexpr mint pow(ll n) const {if (n == 0) return 1;mint res = pow(n >> 1);res *= res;if (n & 1) res *= *this;return res;}constexpr mint inv() const { return pow(mod - 2); }friend istream& operator>>(istream& is, mint& a) noexcept {ll v; is >> v;a = mint(v);return is;}friend ostream& operator<<(ostream& os, const mint& a) noexcept {return os << a.x;}};struct UnionFind{vector<ll> par, size;UnionFind(ll N) : par(N){ //最初はすべてが根であるとして初期化size.resize(N, 1);for (ll i = 0; i < N; i++)par[i] = i;}ll root(ll x){ //データxの木の根を再帰で得るif (par[x] == x)return x;return par[x] = root(par[x]);}void unite(ll x, ll y){ //xとyの木を併合ll rx = root(x);ll ry = root(y);if (rx == ry)return; //同じ木にあるときはそのままif (size[rx] > size[ry]){par[ry] = rx;size[rx] += size[ry];}else{par[rx] = ry;size[ry] += size[rx];}return;}bool same(ll x, ll y){ //2つのデータx,yが属する木が同じならtruell rx = root(x);ll ry = root(y);return rx == ry;}ll treesize(ll x) { return size[root(x)]; }};const int MAX = 2010000;long long fac[MAX], finv[MAX], inv[MAX];// テーブルを作る前処理void COMinit(){fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % mod;inv[i] = mod - inv[mod % i] * (mod / i) % mod;finv[i] = finv[i - 1] * inv[i] % mod;}}// 二項係数計算long long COM(ll n, ll k){if (n < k)return 0;if (n < 0 || k < 0)return 0;return fac[n] * (finv[k] * finv[n - k] % mod) % mod;}vector<ll> enum_div(ll n){ //約数全列挙vector<ll> ret;for (ll i = 1; i * i <= n; ++i){if (n % i == 0){ret.push_back(i);if (i * i != n){ret.push_back(n / i);}}}return ret;}void make_prime(vector<ll> &ret, ll n){ //素因数分解ll x = n;for (ll i = 2; i * i <= x; i++){while (n % i == 0){n /= i;ret.push_back(i);}}if (n != 1){ret.push_back(n);}return;}vector<bool> prime(1000010, true);vector<ll> pri(1000010);vector<bool> isprime(int N){ //素数判定if (N >= 0)prime[0] = false;if (N >= 1)prime[1] = false;for (ll i = 2; i * i <= N; i++){if (!prime[i]){continue;}for (ll j = i * i; j <= N; j += i){if (prime[j])pri[j] = i;prime[j] = false;}}return prime;}map<ll,ll> compression(vector<ll> v){map<ll,ll> ret;ll cnt = 0;sort(v.begin(),v.end());for(ll i=0; i<v.size(); i++){if(!ret.count(v[i])){ret[v[i]] = cnt;cnt++;}}return ret;}//素因数分解: void make_prime(vector<ll> &ret, ll n)//素数判定 : vector<bool> isprime(int N)//約数全列挙: vector<ll> enum_div(ll n)void solve(){ll n, m, k, cnt = 0, sum = 0, ans = 0;cin>>n;ll x,y;cout<<"? "<<1<<endl;cin>>x;cout<<"? "<<n-1<<endl;cin>>y;ll flag=0;if(y-x==(n-2)/2){cout<<"! 2 "<<n-1<<endl;return;}if(y-x<(n-2)/2) flag=1;ll mid,s,t;s=1;t=n-1;ll z;while(t-s>1){mid=(t+s)/2;cout<<"? "<<mid<<endl;cin>>z;if(2*z==mid){if(mid<n/2){cout<<"! "<<mid+1<<" "<<n<<endl;}else{cout<<"! 1 "<<mid<<endl;}return;}if(2*z>mid){if(flag==1) s=mid;else t=mid;}else{if(flag==0) s=mid;else t=mid;}}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);//cout << fixed << setprecision(16);//ll T;//cin>>T;//rep(ca,T)solve();}