#588619 (C++14) No.1306 Exactly 2 Digits

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	carrot46
提出日時	2020-12-03 12:56:03
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	148 ms / 2,000 ms
コード長	4,221 bytes
コンパイル時間	2,025 ms
コンパイル使用メモリ	184,876 KB
実行使用メモリ	24,396 KB
平均クエリ数	1236.78
最終ジャッジ日時	2023-09-24 08:18:27
合計ジャッジ時間	17,920 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	27 ms 23,508 KB
testcase_01	AC	26 ms 23,412 KB
testcase_02	AC	25 ms 23,652 KB
testcase_03	AC	26 ms 23,412 KB
testcase_04	AC	26 ms 24,036 KB
testcase_05	AC	26 ms 24,252 KB
testcase_06	AC	26 ms 23,820 KB
testcase_07	AC	26 ms 23,232 KB
testcase_08	AC	26 ms 23,532 KB
testcase_09	AC	26 ms 23,520 KB
testcase_10	AC	26 ms 24,012 KB
testcase_11	AC	26 ms 23,628 KB
testcase_12	AC	26 ms 23,628 KB
testcase_13	AC	27 ms 23,964 KB
testcase_14	AC	26 ms 23,424 KB
testcase_15	AC	26 ms 23,508 KB
testcase_16	AC	26 ms 23,508 KB
testcase_17	AC	26 ms 23,832 KB
testcase_18	AC	26 ms 23,400 KB
testcase_19	AC	26 ms 23,640 KB
testcase_20	AC	26 ms 23,412 KB
testcase_21	AC	26 ms 23,364 KB
testcase_22	AC	26 ms 24,024 KB
testcase_23	AC	27 ms 23,376 KB
testcase_24	AC	26 ms 24,264 KB
testcase_25	AC	27 ms 23,520 KB
testcase_26	AC	27 ms 23,700 KB
testcase_27	AC	26 ms 23,820 KB
testcase_28	AC	26 ms 23,820 KB
testcase_29	AC	26 ms 23,388 KB
testcase_30	AC	26 ms 24,012 KB
testcase_31	AC	26 ms 23,364 KB
testcase_32	AC	27 ms 23,388 KB
testcase_33	AC	27 ms 23,664 KB
testcase_34	AC	27 ms 23,616 KB
testcase_35	AC	27 ms 23,412 KB
testcase_36	AC	27 ms 23,832 KB
testcase_37	AC	27 ms 23,352 KB
testcase_38	AC	27 ms 23,400 KB
testcase_39	AC	28 ms 24,264 KB
testcase_40	AC	27 ms 24,036 KB
testcase_41	AC	27 ms 23,400 KB
testcase_42	AC	27 ms 24,012 KB
testcase_43	AC	27 ms 23,400 KB
testcase_44	AC	28 ms 23,832 KB
testcase_45	AC	28 ms 23,664 KB
testcase_46	AC	30 ms 23,412 KB
testcase_47	AC	30 ms 24,276 KB
testcase_48	AC	32 ms 23,520 KB
testcase_49	AC	32 ms 24,036 KB
testcase_50	AC	33 ms 24,360 KB
testcase_51	AC	35 ms 23,628 KB
testcase_52	AC	37 ms 24,312 KB
testcase_53	AC	38 ms 24,312 KB
testcase_54	AC	36 ms 23,640 KB
testcase_55	AC	40 ms 23,352 KB
testcase_56	AC	42 ms 23,364 KB
testcase_57	AC	43 ms 24,324 KB
testcase_58	AC	45 ms 23,364 KB
testcase_59	AC	44 ms 23,820 KB
testcase_60	AC	51 ms 23,652 KB
testcase_61	AC	56 ms 23,628 KB
testcase_62	AC	55 ms 23,628 KB
testcase_63	AC	58 ms 24,324 KB
testcase_64	AC	56 ms 23,664 KB
testcase_65	AC	58 ms 23,820 KB
testcase_66	AC	65 ms 23,508 KB
testcase_67	AC	66 ms 23,652 KB
testcase_68	AC	65 ms 23,652 KB
testcase_69	AC	71 ms 23,208 KB
testcase_70	AC	70 ms 24,048 KB
testcase_71	AC	74 ms 23,376 KB
testcase_72	AC	75 ms 23,616 KB
testcase_73	AC	75 ms 23,412 KB
testcase_74	AC	86 ms 23,628 KB
testcase_75	AC	78 ms 23,412 KB
testcase_76	AC	90 ms 23,400 KB
testcase_77	AC	95 ms 23,412 KB
testcase_78	AC	104 ms 24,024 KB
testcase_79	AC	111 ms 23,628 KB
testcase_80	AC	116 ms 24,372 KB
testcase_81	AC	98 ms 23,520 KB
testcase_82	AC	120 ms 23,652 KB
testcase_83	AC	123 ms 23,832 KB
testcase_84	AC	137 ms 23,652 KB
testcase_85	AC	144 ms 24,348 KB
testcase_86	AC	115 ms 23,664 KB
testcase_87	AC	122 ms 24,024 KB
testcase_88	AC	148 ms 23,412 KB
testcase_89	AC	123 ms 24,276 KB
testcase_90	AC	108 ms 23,376 KB
testcase_91	AC	119 ms 24,048 KB
testcase_92	AC	108 ms 24,360 KB
testcase_93	AC	130 ms 23,400 KB
testcase_94	AC	108 ms 24,036 KB
testcase_95	AC	115 ms 24,276 KB
testcase_96	AC	107 ms 24,360 KB
testcase_97	AC	107 ms 23,400 KB
testcase_98	AC	102 ms 24,012 KB
testcase_99	AC	119 ms 23,424 KB
testcase_100	AC	120 ms 24,324 KB
testcase_101	AC	130 ms 23,412 KB
testcase_102	AC	105 ms 23,400 KB
testcase_103	AC	114 ms 23,652 KB
testcase_104	AC	115 ms 23,820 KB
testcase_105	AC	116 ms 24,372 KB
testcase_106	AC	105 ms 23,652 KB
testcase_107	AC	116 ms 24,024 KB
testcase_108	AC	109 ms 24,324 KB
testcase_109	AC	133 ms 23,400 KB
testcase_110	AC	106 ms 23,412 KB
testcase_111	AC	112 ms 24,012 KB
testcase_112	AC	100 ms 23,508 KB
testcase_113	AC	133 ms 24,372 KB
testcase_114	AC	141 ms 24,036 KB
testcase_115	AC	118 ms 24,396 KB
testcase_116	AC	140 ms 24,336 KB
testcase_117	AC	121 ms 23,520 KB
testcase_118	AC	131 ms 24,048 KB
testcase_119	AC	110 ms 24,012 KB
testcase_120	AC	104 ms 24,264 KB
testcase_121	AC	123 ms 24,012 KB
testcase_122	AC	121 ms 23,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
//#include <chrono>
//#pragma GCC optimize("O2")
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()

using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

ll N,M,H,W,K,A,B;
string S;
using P = pair<ll, ll>;
const ll INF = (1LL<<60);

template<class T> bool chmin(T &a, const T &b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T &b){
    if(a < b) {a = b; return true;}
    else return false;
}
template<class T> void print_vector(std::vector<T> v,bool endline = true){
    if(!v.empty()){
        for(std::size_t i{}; i<v.size()-1; ++i) std::cout<<v[i]<<" ";
        std::cout<<v.back();
    }
    if(endline) std::cout<<std::endl;
}

bool debug = false;
vec aite;

P Q(int i, int j){
    if(debug){
        int p = aite[i]/N - aite[j]/N, q = aite[i]%N - aite[j]%N;
        if(p > q) swap(p, q);
        return make_pair(p, q);
    }else {
        cout << "? " << i + 1 << ' ' << j + 1 << endl;
        int p, q;
        cin >> p >> q;
        return make_pair(p, q);
    }
}

vec calc(P p, int n, int o, bool pr = false){
    vec res;
    rep(_, 2){
        int nn = p.first, oo = p.second;
        nn += n; oo += o;
        if(pr) cout<<nn<<' '<<oo<<' '<<(nn >= 1 && nn < N && oo >= 0 && oo < N)<<endl;
        if(nn >= 1 && nn < N && oo >= 0 && oo < N) res.push_back(nn * N + oo);
        if(p.first == p.second) break;
        swap(p.first, p.second);
    }
    if(pr) print_vector(res);
    return res;
}

vec solve(){
    map<P, vector<int> > id;
    reps(i, 1, N * N - N){
        id[Q(i, 0)].push_back(i);
    }
    P big = id.rbegin()->first, small = id.begin()->first;
    if(N == 2){
        if(small.first == -1) cout<<"! 3 2"<<endl;
        else cout<<"! 2 3"<<endl;
        return {};
    }
    int n_bit, one_bit, small_id = id.begin()->second[0], big_id = id.rbegin()->second[0];
    if(small.first == 0){
        one_bit = 0; n_bit = 1;
    }else if(big.first < 0){
        one_bit = n_bit = N - 1;
    }else if(big.first - small.first == N - 1) {
        one_bit = -small.first; n_bit = 1 - small.second;
    }else{
        one_bit = -small.second; n_bit = 1 - small.first;
    }
    vec ans(N * N - N);
    ans[0] = n_bit * N + one_bit;
    for(pair<P, vector<int> > pv : id){
        vec kouho = calc(pv.first, n_bit, one_bit);
        if(debug && kouho.empty()){
            cout<<N<<endl;
            print_vector(aite);
            cout<<n_bit<<' '<<one_bit<<endl;
            cout<<pv.first.first<<' '<<pv.first.second<<endl;
            calc(pv.first, n_bit, one_bit, true);
            exit(0);
        }
        assert(!kouho.empty());
        if(pv.second.size() == 1){
            ans[pv.second[0]] = kouho[0];
        }else {
            vec nx_kouho;
            if(n_bit == one_bit) nx_kouho = calc(Q(pv.second[0], small_id), 1, 0);
            else nx_kouho = calc(Q(pv.second[0], big_id), N - 1, N - 1);
            assert(!nx_kouho.empty());
            rep(i, 2) {
                if (kouho[i] == nx_kouho[0] || (nx_kouho.size() == 2 && kouho[i] == nx_kouho[1])) ans[pv.second[0]] = kouho[i];
                else ans[pv.second[1]] = kouho[i];
            }
        }
    }
    if(debug){
        return ans;
    }else {
        cout << "! ";
        print_vector(ans);
        return {};
    }
}

int main(){
    //cin.tie(nullptr);
    //ios::sync_with_stdio(false);
    cin>>N;
    solve();
    /*
    random_device seed;
    mt19937 mt(seed());
    uniform_int_distribution<> randN(3, 10), randA(0, 10000000);
    rep(_, 1000){
        N = randN(mt);
        aite.resize(N * N - N);
        set<ll> a;
        reps(i, N, N * N) a.insert(i);
        Rreps(i, N * N - N + 1, 1){
            int num = randA(mt)%i;
            auto ite = a.begin();
            rep(j, num) ++ite;
            aite[N * N - N - i] = *ite;
            a.erase(ite);
        }
        vec res = solve();
        if(aite != res){
            print_vector(aite);
            print_vector(res);
            return 0;
        }
    }
     */
}

yukicoder

結果

テストケース

ソースコード