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

提出ソース

結果

問題	No.1306 Exactly 2 Digits
ユーザー	harady_a_human
提出日時	2020-11-24 00:56:30
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	146 ms / 2,000 ms
コード長	14,391 bytes
コンパイル時間	2,693 ms
コンパイル使用メモリ	211,728 KB
実行使用メモリ	25,452 KB
平均クエリ数	1419.06
最終ジャッジ日時	2024-07-17 07:32:24
合計ジャッジ時間	18,116 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	27 ms 24,812 KB
testcase_01	AC	24 ms 24,556 KB
testcase_02	AC	24 ms 24,836 KB
testcase_03	AC	24 ms 24,836 KB
testcase_04	AC	23 ms 24,580 KB
testcase_05	AC	24 ms 24,580 KB
testcase_06	AC	24 ms 24,820 KB
testcase_07	AC	24 ms 24,952 KB
testcase_08	AC	24 ms 24,580 KB
testcase_09	AC	24 ms 24,836 KB
testcase_10	AC	24 ms 24,580 KB
testcase_11	AC	23 ms 25,220 KB
testcase_12	AC	24 ms 24,964 KB
testcase_13	AC	23 ms 25,196 KB
testcase_14	AC	23 ms 25,196 KB
testcase_15	AC	24 ms 25,452 KB
testcase_16	AC	24 ms 24,940 KB
testcase_17	AC	23 ms 24,940 KB
testcase_18	AC	24 ms 25,196 KB
testcase_19	AC	23 ms 24,556 KB
testcase_20	AC	24 ms 24,556 KB
testcase_21	AC	24 ms 25,192 KB
testcase_22	AC	24 ms 25,196 KB
testcase_23	AC	24 ms 24,812 KB
testcase_24	AC	25 ms 24,812 KB
testcase_25	AC	25 ms 24,940 KB
testcase_26	AC	24 ms 25,184 KB
testcase_27	AC	24 ms 25,196 KB
testcase_28	AC	24 ms 24,940 KB
testcase_29	AC	24 ms 24,812 KB
testcase_30	AC	24 ms 25,196 KB
testcase_31	AC	25 ms 25,196 KB
testcase_32	AC	24 ms 25,424 KB
testcase_33	AC	25 ms 24,556 KB
testcase_34	AC	24 ms 25,196 KB
testcase_35	AC	25 ms 25,196 KB
testcase_36	AC	25 ms 25,196 KB
testcase_37	AC	25 ms 24,556 KB
testcase_38	AC	25 ms 25,196 KB
testcase_39	AC	24 ms 24,812 KB
testcase_40	AC	24 ms 24,812 KB
testcase_41	AC	24 ms 24,812 KB
testcase_42	AC	25 ms 25,196 KB
testcase_43	AC	25 ms 24,940 KB
testcase_44	AC	27 ms 25,324 KB
testcase_45	AC	27 ms 24,556 KB
testcase_46	AC	27 ms 24,940 KB
testcase_47	AC	29 ms 24,940 KB
testcase_48	AC	30 ms 24,812 KB
testcase_49	AC	31 ms 24,812 KB
testcase_50	AC	32 ms 24,940 KB
testcase_51	AC	32 ms 25,196 KB
testcase_52	AC	36 ms 24,812 KB
testcase_53	AC	38 ms 24,940 KB
testcase_54	AC	35 ms 24,556 KB
testcase_55	AC	40 ms 25,452 KB
testcase_56	AC	42 ms 25,452 KB
testcase_57	AC	44 ms 24,940 KB
testcase_58	AC	46 ms 25,196 KB
testcase_59	AC	44 ms 24,812 KB
testcase_60	AC	51 ms 24,940 KB
testcase_61	AC	53 ms 24,796 KB
testcase_62	AC	56 ms 24,940 KB
testcase_63	AC	58 ms 25,196 KB
testcase_64	AC	59 ms 25,452 KB
testcase_65	AC	63 ms 25,196 KB
testcase_66	AC	67 ms 25,196 KB
testcase_67	AC	72 ms 24,940 KB
testcase_68	AC	70 ms 24,812 KB
testcase_69	AC	74 ms 24,940 KB
testcase_70	AC	76 ms 25,196 KB
testcase_71	AC	79 ms 25,452 KB
testcase_72	AC	82 ms 25,196 KB
testcase_73	AC	76 ms 25,312 KB
testcase_74	AC	93 ms 25,180 KB
testcase_75	AC	88 ms 25,196 KB
testcase_76	AC	99 ms 25,196 KB
testcase_77	AC	103 ms 25,452 KB
testcase_78	AC	109 ms 24,812 KB
testcase_79	AC	112 ms 24,556 KB
testcase_80	AC	114 ms 25,052 KB
testcase_81	AC	106 ms 24,812 KB
testcase_82	AC	125 ms 24,812 KB
testcase_83	AC	131 ms 24,556 KB
testcase_84	AC	133 ms 25,196 KB
testcase_85	AC	142 ms 25,196 KB
testcase_86	AC	128 ms 24,812 KB
testcase_87	AC	136 ms 24,556 KB
testcase_88	AC	141 ms 24,812 KB
testcase_89	AC	130 ms 24,940 KB
testcase_90	AC	113 ms 25,196 KB
testcase_91	AC	130 ms 24,812 KB
testcase_92	AC	126 ms 24,812 KB
testcase_93	AC	134 ms 25,452 KB
testcase_94	AC	128 ms 25,440 KB
testcase_95	AC	129 ms 24,812 KB
testcase_96	AC	122 ms 24,556 KB
testcase_97	AC	115 ms 24,812 KB
testcase_98	AC	114 ms 24,812 KB
testcase_99	AC	127 ms 24,556 KB
testcase_100	AC	129 ms 24,556 KB
testcase_101	AC	135 ms 25,196 KB
testcase_102	AC	120 ms 25,452 KB
testcase_103	AC	125 ms 25,052 KB
testcase_104	AC	131 ms 24,556 KB
testcase_105	AC	133 ms 25,324 KB
testcase_106	AC	116 ms 24,556 KB
testcase_107	AC	136 ms 24,812 KB
testcase_108	AC	119 ms 24,940 KB
testcase_109	AC	142 ms 24,556 KB
testcase_110	AC	123 ms 24,940 KB
testcase_111	AC	125 ms 25,452 KB
testcase_112	AC	113 ms 24,940 KB
testcase_113	AC	142 ms 25,196 KB
testcase_114	AC	137 ms 24,556 KB
testcase_115	AC	135 ms 24,940 KB
testcase_116	AC	146 ms 24,940 KB
testcase_117	AC	137 ms 24,940 KB
testcase_118	AC	144 ms 24,556 KB
testcase_119	AC	129 ms 25,196 KB
testcase_120	AC	114 ms 25,196 KB
testcase_121	AC	133 ms 25,196 KB
testcase_122	AC	131 ms 24,812 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

// #include <iostream> // cout, endl, cin
// #include <string> // string, to_string, stoi
// #include <vector> // vector
// #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
// #include <utility> // pair, make_pair
// #include <tuple> // tuple, make_tuple
// #include <cstdint> // int64_t, int*_t
// #include <cstdio> // printf
// #include <map> // map
// #include <queue> // queue, priority_queue
// #include <set> // set
// #include <stack> // stack
// #include <deque> // deque
// #include <unordered_map> // unordered_map
// #include <unordered_set> // unordered_set
// #include <bitset> // bitset
// #include <climits>
// #include <cmath>
// #include <iomanip>
// #include <functional>
// #include <numeric>
// #include <random>
 
using namespace std;

#define int long long
#define pb push_back
#define eb emplace_back
// #define F first
// #define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(int)(b);(i)++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int (i)=(a);(i)>=(int)(b);(i)--)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end())
#define Double double
// #define endl '\n'
 
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>; 
using ll = long long;
using ld = long double;
using UnWeightedGraph = vector<vector<int>>;
ll INF = LLONG_MAX / 4 - 100;
int IINF = INT_MAX / 4;
ll mod = 1e9 + 7;
int dx[] = {1,0,-1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
 
long double pi = 3.141592653589793238;
    
class fact {
public:
    long long fmod = 1e9+7;
    vector<long long> fac, finv, inv;
    fact (int n, long long Mod = 1e9+7) {
        fmod = Mod;
        fac = vector<long long>(n + 1, 0);
        finv = vector<long long>(n + 1, 0);
        inv = vector<long long>(n + 1, 0);
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1; 
        for (int i = 2; i < n + 1; i++) {
            fac[i] = fac[i-1] * i % fmod;
            inv[i] = mod - inv[mod%i] * (mod/i) % mod;
            finv[i] = finv[i-1] * inv[i] % mod;
        }
    }
    ll nCr(ll n, ll r) {if(n < r) return 0; return fac[n] * finv[r] % fmod * finv[n-r] % fmod;}
    ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%fmod;}a = a * a%fmod; b >>= 1;}return c;}
    inline int operator [] (int i) {return fac[i];}
    ll DeBuG(ll n, ll r);
};
    
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return (a / GCD(a, b)) * (b / GCD(a, b)) * GCD(a, b);}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%mod;}a = a * a%mod; b >>= 1;}return c;}
ld POW(ld a, ll b) {ld c = 1; while (b > 0) {if (b & 1) {c = a * c;}a = a * a; b >>= 1;}return c;}
void PRI(ll n) {bool a[n + 1]; for (int i = 0; i < n + 1; i++) {a[i] = 1;}for (int i = 2; i < n + 1; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}
bool isSqrt(ll a) {return pow(sqrt(a),2) == a ? 1 : 0;}
void YesNo(bool a) {if (a) cout << "Yes"; else cout << "No"; cout << endl;}
void yesno(bool a) {if (a) cout << "yes"; else cout << "no"; cout << endl;}
void YESNO(bool a) {if (a) cout << "YES"; else cout << "NO"; cout << endl;}
double dis(int x1, int x2, int y1, int y2) {
    return sqrt((double)abs(x1-x2)*(double)abs(x1-x2)+(double)abs(y1-y2)*(double)abs(y1-y2));
}
int ceili(int x, int y) {
    if (x % y == 0) return x / y;
    else return x / y + 1;
}
unsigned int randxor() {
    static unsigned int x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned int t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}
 
uint64_t xor64(void) {
    static uint64_t x = 88172645463325252ULL;
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
}

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int invs(vector<int> &vec) {
    vector<pair<int, int>> val(vec.size());
    vector<int> bit(vec.size()+1);
    for (int i = 0; i < vec.size(); i++) {
        val[i] = {vec[i], i+1};
    }
    sort(val.rbegin(), val.rend());
    int ret = 0;
    for (int i = 0; i < val.size(); i++) {
        for (int j = val[i].second; j > 0; j -= j & -j) ret += bit[j];
        for (int j = val[i].second; j <= vec.size(); j += j & -j) bit[j]++;
    }
    return ret;
}

void AND(int i, int j) {
    cout << "AND " << i << " " << j << endl;
}
void OR(int i, int j) {
    cout << "OR " << i << " " << j << endl;
}
void XOR(int i, int j) {
    cout << "XOR " << i << " " << j << endl;
}

int co(int n, int i, int j) {
    return (n*i+j);
}

pair<int, int> req(int i, int j) {
    cout << "? " << i << " " << j << endl;
    int t1, t2; cin >> t1 >> t2; return {t1, t2};
}

void solve() {
    int n; cin >> n;
    // if (n != 4) exit(0);
    if (n == 2) {
        auto res = req(1, 2);
        if (res.first == -1) {
            cout << "! " << 2 << " " << 3 << endl;
        } else {
            cout << "! " << 3 << " " << 2 << endl;
        }
        return;
    }
    map<int, int> cnt;
    map<pair<int, int>, vector<int>> idx;
    vector<pair<int, int>> res(n*n-n);
    vector<int> ans(n*n-n, -1);
    // cout << 1 << endl;
    rep (_, n*n-n-1) {
        res[_+1] = req(_+2, 1);
        cnt[res[_+1].first]++, cnt[res[_+1].second]++;
        idx[{res[_+1]}].pb(_+1);
    }
    map<int, int> posi;
    // cout << 1 << endl;
    for (auto e : cnt) if (e.first > 0) posi[e.second]++;
    if (posi.size() == 0) {

        // cout << 1 << endl;

        vector<int> dgs({n-1, n-1});
        // DEBUG(dgs);
        ans[0] = co(n, dgs[0], dgs[1]);
        int minp = idx[minmax(-dgs[0]+1, -dgs[1])][0];
        ans[minp] = n;
        rep (i, n*n-n) {
            if (ans[i] != -1) continue;
            // cout << i << endl;
            if (res[i].first == res[i].second) ans[i] = co(n, dgs[0]+res[i].first, dgs[1]+res[i].first);
            else {
                if (dgs[0]+res[i].first >= n || dgs[1]+res[i].second >= n) {
                    ans[i] = co(n, dgs[0]+res[i].second, dgs[1]+res[i].first);
                    continue;
                }
                if (dgs[0]+res[i].second >= n || dgs[1]+res[i].first >= n) {
                    ans[i] = co(n, dgs[0]+res[i].first, dgs[1]+res[i].second);
                    continue;
                }
                set<int> c1{co(n, n-1+res[i].first, n-1+res[i].second), 
                co(n, n-1+res[i].second, n-1+res[i].first)};
                for (auto e : c1) if (e > n*n-1) c1.erase(e);
                if (c1.size() == 1) {
                    ans[i] = *c1.begin();
                    continue;
                }
                pair<int, int> tmp = req(i+1, minp+1);
                set<int> c2{co(n, 1+tmp.first, tmp.second), co(n, 1+tmp.second, tmp.first)};
                for (auto e : c1) {
                    for (auto e2 : c2) {
                        // cout << e << " " << e2 << endl;
                        if (e == e2) ans[i] = e;
                    }
                }
                c1.erase(ans[i]);
                for (auto e : idx[res[i]]) if (ans[e] == -1) ans[e] = *c1.begin();
            }
        }
    } /*else if (posi.size() == 1)  {
        ans[0] = co(n, n-1-posi.begin()->second, n-1-posi.begin()->second);
        vector<int> dgs({n-1-posi.begin()->second, n-1-posi.begin()->second});
        int minp = idx[{-(n-1-posi.begin()->second), -(n-1-posi.begin()->second)+1}][0];
        ans[minp] = n;
        rep (i, n*n-n) {
            if (ans[i] != -1) continue;
            if (res[i].first == res[i].second) ans[i] = co (n, dgs[0]+res[i].first, dgs[1]+res[i].first);
            else {
                set<int> c1{co(n, dgs[0]+res[i].first, dgs[1]+res[i].second), 
                co(n, dgs[0]+res[i].second, dgs[1]+res[i].first)};
                pair<int, int> tmp = req(i+1, minp+1);
                set<int> c2{co(n, 1+tmp.first, tmp.second), co(n, 1+tmp.second, tmp.first)};
                for (auto e : c1) {
                    for (auto e2 : c2) {
                        // cout << e << " " << e2 << endl;
                        if (e == e2) ans[i] = e;
                    }
                }
                c1.erase(ans[i]);
                for (auto e : idx[res[i]]) if (ans[e] == -1) ans[e] = *c1.begin();
            }
        }
    } */else if (posi.begin()->first == n) {

    // cout << 2 << endl;

        vector<int> dgs({n-1-(posi.size()!=1)*posi.rbegin()->second-posi.begin()->second, n-1-(posi.size()!=1)*posi.rbegin()->second});
        // DEBUG(dgs);
        ans[0] = co(n, dgs[0], dgs[1]);
        int minp = idx[minmax(-dgs[0]+1, -dgs[1])][0];
        // cout << ans[0] << " " << minp << endl;
        ans[minp] = n;
        rep (i, n*n-n) {
            if (ans[i] != -1) continue;
            if (res[i].first == res[i].second) ans[i] = co (n, dgs[0]+res[i].first, dgs[1]+res[i].first);
            else {
                if (dgs[0]+res[i].first >= n || dgs[1]+res[i].second >= n) {
                    ans[i] = co(n, dgs[0]+res[i].second, dgs[1]+res[i].first);
                    continue;
                }
                if (dgs[0]+res[i].second >= n || dgs[1]+res[i].first >= n) {
                    ans[i] = co(n, dgs[0]+res[i].first, dgs[1]+res[i].second);
                    continue;
                }
                set<int> c1{co(n, dgs[0]+res[i].first, dgs[1]+res[i].second), 
                co(n, dgs[0]+res[i].second, dgs[1]+res[i].first)};
                for (auto e : c1) if (e > n*n-1) c1.erase(e);
                if (c1.size() == 1) {
                    ans[i] = *c1.begin();
                    continue;
                }
                pair<int, int> tmp = req(i+1, minp+1);
                set<int> c2{co(n, 1+tmp.first, tmp.second), co(n, 1+tmp.second, tmp.first)};
                for (auto e : c1) {
                    for (auto e2 : c2) {
                        // cout << e << " " << e2 << endl;
                        if (e == e2) ans[i] = e;
                    }
                }
                c1.erase(ans[i]);
                for (auto e : idx[res[i]]) if (ans[e] == -1) ans[e] = *c1.begin();
            }
        }
    } else if (posi.begin()->first == n-1) {

        // cout << 3 << endl;

        vector<int> dgs({n-1-(posi.size()!=1)*posi.rbegin()->second, n-1-(posi.size()!=1)*posi.rbegin()->second-posi.begin()->second});
        ans[0] = co(n, dgs[0], dgs[1]);
        int maxp = idx[minmax(n-1-dgs[0], n-1-dgs[1])][0];
        ans[maxp] = n*n-1;
        rep (i, n*n-n) {
            if (ans[i] != -1) continue;
            if (res[i].first == res[i].second) ans[i] = co (n, dgs[0]+res[i].first, dgs[1]+res[i].first);
            else {
                if (dgs[0]+res[i].first >= n || dgs[1]+res[i].second >= n) {
                    ans[i] = co(n, dgs[0]+res[i].second, dgs[1]+res[i].first);
                    continue;
                }
                if (dgs[0]+res[i].second >= n || dgs[1]+res[i].first >= n) {
                    ans[i] = co(n, dgs[0]+res[i].first, dgs[1]+res[i].second);
                    continue;
                }
                set<int> c1{co(n, dgs[0]+res[i].first, dgs[1]+res[i].second), 
                co(n, dgs[0]+res[i].second, dgs[1]+res[i].first)};
                for (auto e : c1) if (e > n*n-1) c1.erase(e);
                if (c1.size() == 1) {
                    ans[i] = *c1.begin();
                    continue;
                }
                pair<int, int> tmp = req(maxp+1, i+1);
                set<int> c2{co(n, n-1-tmp.first, n-1-tmp.second), co(n, n-1-tmp.second, n-1-tmp.first)};
                for (auto e : c1) {
                    for (auto e2 : c2) {
                        // cout << e << " " << e2 << endl;
                        if (e == e2) ans[i] = e;
                    }
                }
                c1.erase(ans[i]);
                for (auto e : idx[res[i]]) if (ans[e] == -1) ans[e] = *c1.begin();
            }
        }
    } else {

        // cout << 4 << endl;

        ans[0] = co(n, n-1-posi.begin()->second, n-1-posi.begin()->second);
        vector<int> dgs({n-1-posi.begin()->second, n-1-posi.begin()->second});
        int minp = idx[minmax(-(n-1-posi.begin()->second), -(n-1-posi.begin()->second)+1)][0];
        ans[minp] = n;
        rep (i, n*n-n) {
            if (ans[i] != -1) continue;
            if (res[i].first == res[i].second) ans[i] = co (n, dgs[0]+res[i].first, dgs[1]+res[i].first);
            else {
                if (dgs[0]+res[i].first >= n || dgs[1]+res[i].second >= n) {
                    ans[i] = co(n, dgs[0]+res[i].second, dgs[1]+res[i].first);
                    continue;
                }
                if (dgs[0]+res[i].second >= n || dgs[1]+res[i].first >= n) {
                    ans[i] = co(n, dgs[0]+res[i].first, dgs[1]+res[i].second);
                    continue;
                }
                set<int> c1{co(n, dgs[0]+res[i].first, dgs[1]+res[i].second), 
                co(n, dgs[0]+res[i].second, dgs[1]+res[i].first)};
                for (auto e : c1) if (e > n*n-1) c1.erase(e);
                if (c1.size() == 1) {
                    ans[i] = *c1.begin();
                    continue;
                }
                pair<int, int> tmp = req(i+1, minp+1);
                set<int> c2{co(n, 1+tmp.first, tmp.second), co(n, 1+tmp.second, tmp.first)};
                for (auto e : c1) {
                    for (auto e2 : c2) {
                        // cout << e << " " << e2 << endl;
                        if (e == e2) ans[i] = e;
                    }
                }
                c1.erase(ans[i]);
                for (auto e : idx[res[i]]) if (ans[e] == -1) ans[e] = *c1.begin();
            }
        }
    }
    cout << "! ";
    DEBUG(ans);
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
}

yukicoder

結果

テストケース

ソースコード