結果

問題 No.2368 I love a square root of 2
ユーザー Kak1_n0_taneKak1_n0_tane
提出日時 2021-07-04 03:43:25
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 2,467 bytes
コンパイル時間 1,003 ms
コンパイル使用メモリ 108,888 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-07 06:45:06
合計ジャッジ時間 1,964 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
9,472 KB
testcase_01 AC 6 ms
9,472 KB
testcase_02 AC 18 ms
11,264 KB
testcase_03 AC 7 ms
9,472 KB
testcase_04 AC 7 ms
9,600 KB
testcase_05 AC 7 ms
9,472 KB
testcase_06 AC 8 ms
9,472 KB
testcase_07 AC 7 ms
9,600 KB
testcase_08 AC 7 ms
9,472 KB
testcase_09 AC 6 ms
9,472 KB
testcase_10 AC 7 ms
9,472 KB
testcase_11 AC 8 ms
9,472 KB
testcase_12 AC 8 ms
9,472 KB
testcase_13 AC 15 ms
10,880 KB
testcase_14 AC 15 ms
11,008 KB
testcase_15 AC 16 ms
11,264 KB
testcase_16 AC 13 ms
10,496 KB
testcase_17 AC 7 ms
9,472 KB
testcase_18 AC 7 ms
9,472 KB
testcase_19 AC 7 ms
9,472 KB
testcase_20 AC 7 ms
9,600 KB
testcase_21 AC 18 ms
11,392 KB
testcase_22 AC 18 ms
11,264 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:78:45: warning: 'seisuu' may be used uninitialized [-Wmaybe-uninitialized]
   78 |     vector<pair<ll,ll>> amari(Vec_cum[seisuu]); // pair(amari, a+√2b の a)
      |                                             ^
main.cpp:70:8: note: 'seisuu' was declared here
   70 |     ll seisuu;
      |        ^~~~~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <iomanip>
#include <vector>
#include <cstring>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef vector<vector<int>> Graph;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

//main area
int main(){
    /*
    cout << fixed << setprecision(20);
    ll bunbo = 1;
    ll bunshi = 1;
    for(int i=0;i<20;i++){
        bunshi += bunbo;
        swap(bunshi, bunbo);
        bunshi += bunbo;
        ld r2 = (bunshi*1.0) / (bunbo*1.0);
        cout << bunshi << " / " << bunbo << " : " << r2 << endl;
    }
    */
    ll UP_r2 = 54608393, DOWN_r2 = 38613965; // A = DOWN_r2 * x + UP_r2 * y
    vector<ll> Vec_seisuu(200000);
    vector<ll> Vec(200000, 0);
    vector<ll> Vec_cum(200000, 0);
    vector<ll> Vec_cum2(200000, 0);
    for(int i = 0;i < 200000;i++){
        ll i_r2 = (UP_r2 * i) / DOWN_r2; // i√2 の整数部分
        Vec_seisuu[i] = i_r2;
        if(i_r2 < 200000) Vec[i_r2] = 1;
    }
    for(int i = 0;i < 200000;i++){
        if(i == 0) Vec_cum[i] = Vec[i];
        else Vec_cum[i] = Vec_cum[i-1] + Vec[i];
    }
    for(int i = 0;i < 200000;i++){
        if(i == 0) Vec_cum2[i] = Vec_cum[i];
        else Vec_cum2[i] = Vec_cum2[i-1] + Vec_cum[i];
    }
    /*
    rep(i,11) cout << Vec[i] << ' ';
    cout << endl;
    rep(i,11) cout << Vec_cum[i] << ' ';
    cout << endl;
    rep(i,11) cout << Vec_cum2[i] << ' ';
    cout << endl;
    */

    ll N;
    cin >> N;
    if(N == 1){
        cout << "0 0" << endl;
        return 0;
    }
    ll seisuu;
    for(int i=0;i<200000-1;i++){
        if(Vec_cum2[i] < N && N <= Vec_cum2[i+1]){
            seisuu = i+1;
            break;
        }
    }
    // cout << seisuu << endl;
    vector<pair<ll,ll>> amari(Vec_cum[seisuu]); // pair(amari, a+√2b の a)
    for(int i = 0;i < Vec_cum[seisuu];i++){
        ll a = i*UP_r2 % DOWN_r2;
        amari[i] = make_pair(a, i);
    }
    sort(amari.begin(),amari.end());
    ll Num = N-Vec_cum2[seisuu-1]-1;
    // B = amari[Num]
    cout << seisuu - Vec_seisuu[amari[Num].second] << ' ' << amari[Num].second << endl;
}
/*



}
*/
0