結果

問題 No.3743 World Mapper
コンテスト
ユーザー edon8618
提出日時 2026-09-19 17:29:21
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 12,341 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,549 ms
コンパイル使用メモリ 394,600 KB
実行使用メモリ 9,952 KB
最終ジャッジ日時 2026-09-19 17:29:35
合計ジャッジ時間 11,085 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 4
部分点2 10 % AC * 8 WA * 1
部分点3 10 % AC * 8 WA * 1 TLE * 1 -- * 4
部分点4 10 % AC * 8 WA * 1 TLE * 1 -- * 9
部分点5 10 % AC * 8 WA * 1 TLE * 1 -- * 14
部分点6 10 % AC * 8 WA * 1 TLE * 1 -- * 19
部分点7 10 % AC * 8 WA * 1 TLE * 1 -- * 24
部分点8 10 % AC * 8 WA * 1 TLE * 1 -- * 29
部分点9 10 % AC * 8 WA * 1 TLE * 1 -- * 34
満点 10 % AC * 8 WA * 1 TLE * 1 -- * 39
合計 5 * 10% = 50 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;



// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;

#define ll long long
#define ld long double
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define vi vector<int>
#define vl vector<ll>
#define vd vector<double>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

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;
}


// #define ll int
// #define ll int128_t
// #define ll int256_t
// #define ll cpp_int


constexpr ll inf = (1ll << 62);
// constexpr ll inf = (1 << 30);
// const double PI=3.1415926535897932384626433832795028841971;

uint32_t xor_x = 123456789, xor_y = 362436069, xor_z = 521288629, xor_w = 88675123;
inline uint32_t xor_next() {
    uint32_t t = xor_x ^ (xor_x << 11);
    xor_x = xor_y; xor_y = xor_z; xor_z = xor_w;
    return xor_w = (xor_w ^ (xor_w >> 19)) ^ (t ^ (t >> 8));
}
inline int rnd(int max_val) { return xor_next() % max_val; }


struct Timer {
    std::chrono::steady_clock::time_point start_time;

    Timer() {
        reset();
    }

    // 測定の起点リセット用
    void reset() {
        start_time = std::chrono::steady_clock::now();
    }

    // スタートからの経過時間をミリ秒(msec)で返す
    long long get_ms() const {
        auto now = std::chrono::steady_clock::now();
        return std::chrono::duration_cast<std::chrono::milliseconds>(now - start_time).count();
    }
};

// ll rui(ll a,ll b){
//     if(b==0)return 1;
//     if(b%2==1) return a*rui(a*a,b/2);
//     return rui(a*a,b/2);
// }

// vl fact;
// ll kai(ll n){
//     fact.resize(n,1);
//     rep(i,n-1)fact[i+1]=fact[i]*(i+1);
// }

// using mint = ld;
using mint = modint998244353;//static_modint<998244353>
// using mint = modint1000000007;//static_modint<1000000007>
// using mint = static_modint<922267487>;   // 多分落とされにくい NOT ntt-friendly
// using mint = static_modint<469762049>;   // ntt-friendly
// using mint = static_modint<167772161>;   // ntt-friendly
// using mint = modint;//mint::set_mod(mod);

// ll const mod=1000000007ll;
// ll const mod=998244353ll;
// ll modrui(ll a,ll b,ll mod){
//     a%=mod;
//     if(b==0)return 1;
//     if(b%2==1) return a*modrui(a*a%mod,b/2,mod)%mod;
//     return modrui(a*a%mod,b/2,mod)%mod;
// }

// void incr(vl &v,ll n){//　n進法
//     ll k=v.size();
//     v[k-1]++;
//     ll now=k-1;
//     while (v[now]>=n)
//     {
//         v[now]=0;
//         if(now==0)break;
//         v[now-1]++;
//         now--;
//     }
//     return;
// }

vector<mint> fact,invf;
void init_modfact(ll sz){
    fact.resize(sz);
    invf.resize(sz);
    fact[0]=1;
    rep(i,sz-1){
        fact[i+1]=fact[i]*(i+1);
    }
    invf[sz-1]=1/fact[sz-1];
    for(ll i=sz-2; i>=0; i--){
        invf[i]=invf[i+1]*(i+1);
    }
}
mint choose(ll n,ll r){
    if(n<r || r<0 || n<0)return 0;
    return fact[n]*invf[r]*invf[n-r];
}

// vector<mint> modpow,invpow;
// void init_modpow(ll x,ll sz){
//     mint inv=1/mint(x);
//     modpow.assign(sz,1);
//     invpow.assign(sz,1);
//     rep(i,sz-1){
//         modpow[i+1]=modpow[i]*x;
//         invpow[i+1]=invpow[i]*inv;
//     }
// }
// long long phi(long long n) {// O(sqrt(n))
//     long long res = n;
//     for (long long i = 2; i * i <= n; i++) {
//         if (n % i == 0) {
//             res -= res / i;
//             while (n % i == 0) n /= i;
//         }
//     }
//     if (n > 1) res -= res / n;
//     return res;
// }







void solve(){
    ll n;
    cin >> n;

    vector<vl> r(n,vl(n-1,0));
    vector<vl> c(n-1,vl(n,0));
    const ll M=300000;
    ll iter=0;
    if(n==1){

        // return;
    }
    if(n==2){
        cout << 
        "199111 119409\n" <<
        "287787\n" <<
        "72619\n";
        return;
    }
    if(n==3){
        cout <<
        "199111 69575 239114\n" <<
        "119409 229869 10822\n" <<
        "287787 72619\n" <<
        "91519 149380\n" <<
        "166585 195573\n";
        return;
    }
    if(n==4){
        cout <<
        "199111 229869 174474 207047\n" <<
        "119409 239114 253238 169645\n" <<
        "69575 10822 288983 132713\n" <<
        "287787 72619 91519\n" <<
        "149380 166585 195573\n" <<
        "170321 153269 15221\n" <<
        "281933 253449 60397\n";
        return;
    }
    if(n==5){
        cout <<
        "199111 239114 288983 34234 175419\n" <<
        "119409 10822 207047 253313 278732\n" <<
        "69575 174474 169645 157460 94861\n" <<
        "229869 253238 132713 149641 127416\n" <<
        "287787 72619 91519 149380\n" <<
        "166585 195573 170321 153269\n" <<
        "15221 281933 253449 60397\n" <<
        "280800 106654 206779 102566\n" <<
        "90347 90040 16209 50044\n";
        return;
    }
    if(n==6){
        cout << 
        "206760 192027 137473 188017 220403 16100\n" <<
        "279971 202643 145037 177750 164401 246975\n" <<
        "41161 188211 294588 270828 169742 146022\n" <<
        "288207 238363 11818 28538 276216 249463\n" <<
        "17323 146452 148053 96138 220870 123633\n" <<
        "96297 228847 134210 32665 179652\n" <<
        "28895 90604 173947 62213 230369\n" <<
        "268434 101748 229439 232413 7556\n" <<
        "134816 125817 156967 237757 240805\n" <<
        "17180 224545 108154 253427 92084\n" <<
        "150340 85876 181960 152616 65534\n";

        return;
    }
    if(n==7){
        cout <<
        "199111 174474 34234 94861 272370 206760 202643\n" <<
        "119409 253238 253313 127416 111098 279971 188211\n" <<
        "69575 288983 157460 76301 22359 41161 238363\n" <<
        "229869 207047 149641 10454 95701 288207 146452\n" <<
        "239114 169645 175419 81391 202387 17323 137473\n" <<
        "10822 132713 278732 67953 270697 192027 145037\n" <<
        "287787 72619 91519 149380 166585 195573\n" <<
        "170321 153269 15221 281933 253449 60397\n" <<
        "280800 106654 206779 102566 90347 90040\n" <<
        "16209 50044 13143 258643 266708 293108\n" <<
        "167797 67699 82362 195301 220330 168599\n" <<
        "96297 228847 134210 32665 179652 28895\n" <<
        "90604 173947 62213 230369 268434 101748\n";

        return;
    }
    if(n==8){
        cout <<
        "81193 155056 294105 56038 226192 100494 295344 275801\n" <<
        "87530 22686 126266 208520 284492 85362 59156 18302\n" <<
        "37965 210243 296997 163629 23260 120151 126318 41596\n" <<
        "270027 269665 208323 243199 141925 4555 134480 243925\n" <<
        "55360 44208 27596 94425 237479 131323 147206 127524\n" <<
        "4003 188369 185864 127852 289452 178920 114346 141741\n" <<
        "139530 103648 171694 128247 221626 125531 50415 264421\n" <<
        "171721 223255 251473 101818 15957 145725 93669\n" <<
        "209923 129500 291204 243394 63692 152064 70000\n" <<
        "716 130719 41059 203924 186852 157793 194111\n" <<
        "178682 82294 7526 292031 233363 103835 283375\n" <<
        "77216 297778 204705 104255 288681 258694 150091\n" <<
        "201970 21221 185040 132796 198315 20925 130056\n" <<
        "45551 56160 156792 129187 149519 164754 221330\n" <<
        "132457 210356 223274 294877 121376 45865 152067\n";

        // return;
    }
    if(n==9){
        cout <<
        "76806 244105 296744 124333 155191 21073 183046 80606 63635\n" <<
        "70258 264777 213679 195315 206746 190242 267325 122024 294118\n" <<
        "17093 76069 294254 268706 143708 12580 9093 159716 23757\n" <<
        "137781 281966 3753 25556 32805 24498 293435 225423 44680\n" <<
        "284352 291948 259871 275463 282316 85287 57357 121830 44342\n" <<
        "173692 175742 188091 140629 217109 33257 72355 105139 86343\n" <<
        "173560 54594 247022 273442 39761 281439 15901 227973 106377\n" <<
        "284424 86836 37328 48732 242154 257408 58846 196194 196437\n" <<
        "88993 297305 156685 166744 23407 100953 65495 191408\n" <<
        "101443 172984 170118 50277 72326 289919 271969 62073\n" <<
        "218269 52916 43749 1493 107274 121392 216743 178867\n" <<
        "200990 259547 74963 242093 63012 267784 210490 97519\n" <<
        "250648 8435 20905 299065 177902 93394 219384 52156\n" <<
        "132841 196978 297575 237066 140108 78885 24983 138848\n" <<
        "234929 51489 280932 224138 164615 141043 93785 136676\n" <<
        "39717 222265 218739 73318 31313 202219 231766 175783\n" <<
        "175801 156735 133097 12663 116331 18840 22718 272714\n";

        return;
    }
    if(n==10){
        cout << 
        "22798 21752 211490 21666 96789 164853 166994 79004 248566 191463\n" <<
        "143033 182159 293683 58634 139100 217014 50471 261380 76394 199419\n" <<
        "21300 1472 283226 242575 225212 184604 140027 175261 219794 165308\n" <<
        "178498 147409 292620 55946 172459 180638 299357 85070 115491 204792\n" <<
        "63544 5525 152860 162865 294324 108156 120938 257734 89529 214583\n" <<
        "113298 190919 148359 182883 213884 281839 111574 191216 43596 223514\n" <<
        "293356 43255 293281 281646 8198 183573 246373 248901 19664 125970\n" <<
        "243460 279406 83107 88972 68696 227927 154527 48622 288553 110708\n" <<
        "194286 127788 206661 151200 164891 285546 283679 135629 252947 235188\n" <<
        "237014 275098 164396 53616 160301 71696 175476 268726 157466\n" <<
        "8458 203004 265164 37823 167740 118175 167301 186501 34092\n" <<
        "80814 194194 277906 296746 76323 296129 255360 131143 138737\n" <<
        "75629 169234 283505 127315 270967 164528 164930 37028 49056\n" <<
        "98140 34535 252979 86243 205630 162509 294659 66109 56882\n" <<
        "91382 16796 128624 118228 53242 256157 154357 235159 234848\n" <<
        "51204 30429 55549 164424 116740 159528 163409 33416 225368\n" <<
        "54126 156055 139141 3498 209850 174288 195754 243366 209555\n" <<
        "113949 245538 27219 132544 206583 6710 167921 161748 117657\n" <<
        "189806 173302 189707 183192 264193 251033 202618 244487 33864\n";
        return;
    }
    while(1){
        rep(i,n)rep(j,n-1){
            r[i][j]=rnd(300000)+1;
            c[j][i]=rnd(300000)+1;
        }

        bool ok=1;
        set<ll> st;
        st.clear();
        
        rep(si,n)rep(sj,n){
            if(!ok)break;
            priority_queue<array<ll,3>,vector<array<ll,3>>,greater<array<ll,3>>> pq;
            pq.push({0,si,sj});
            vector<vl> dist(n,vl(n,inf));
            dist[si][sj]=0;
            while(!pq.empty()){
                auto [d,x,y]=pq.top();
                pq.pop();

                if(dist[x][y]!=d)continue;

                if(x!=n-1 && chmin(dist[x+1][y],d+c[x][y]))pq.push({dist[x+1][y],x+1,y});
                if(x!=0 && chmin(dist[x-1][y],d+c[x-1][y]))pq.push({dist[x-1][y],x-1,y});

                if(y!=n-1 && chmin(dist[x][y+1],d+r[x][y]))pq.push({dist[x][y+1],x,y+1});
                if(y!=0 && chmin(dist[x][y-1],d+r[x][y-1]))pq.push({dist[x][y-1],x,y-1});
            }

            rep(i,n)rep(j,n){
                if(i!=si || j!=sj){
                    st.insert(dist[i][j]);
                }
            }
        }
        if(st.size()==(n*n*(n*n-1))/2)break;
        iter++;
        if(iter%100==0)cout << iter << endl;
    }
    rep(i,n-1){
        cout << "\"";
        rep(j,n)cout <<c[i][j] << " \\"[j==n-1];
        cout << "n\" <<\n";
    }
    rep(i,n){
        cout << "\"";
        rep(j,n-1)cout <<r[i][j] << " \\"[j==n-2];
        cout << "n\" <<\n";
    }
}


int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);


    // ll mx=1234567;
    // vc fl(mx+1,0);
    // for(ll d=2;d<=mx;d++){
    //     if(fl[d])continue;
    //     ll x=d;
    //     ps.push_back(x);
    //     while(x<=mx){
    //         fl[x]=1;
    //         x+=d;
    //     }
    // }

    ll t = 1;
    // cin >> t;
    while (t--){
        solve();
    }
}
0