結果

問題 No.3506 All Distance is Square Number
コンテスト
ユーザー GOTKAKO
提出日時 2026-04-18 07:40:30
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 14,041 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,190 ms
コンパイル使用メモリ 249,268 KB
実行使用メモリ 7,976 KB
最終ジャッジ日時 2026-04-18 07:40:36
合計ジャッジ時間 4,709 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

random_device rnd;
mt19937 mt(rnd());

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

    int N; cin >> N;
{
    if(N == 2){
        cout << 1 << endl;
        cout << "1 2 1" << endl;
        cout << "1 1" << endl;
        return 0;
    }
    if(N == 3){
        cout << 3 << endl;
        cout << "1 2 1" << endl;
        cout << "1 3 4" << endl;
        cout << "2 3 9" << endl;
        cout << "1 1" << endl;
        cout << "1 2" << endl;
        cout << "1 3" << endl;
        return 0;
    }
    if(N == 4){
        cout << 5 << endl;
        cout << "1 2 1" << endl;
        cout << "2 3 3" << endl;
        cout << "3 4 5" << endl;
        cout << "2 3 4" << endl;
        cout << "3 4 9" << endl;
        cout << "1 1" << endl;
        cout << "2 1 2" << endl;
        cout << "3 1 2 3" << endl;
        cout << "1 4" << endl;
        cout << "2 4 3" << endl;
        cout << "1 5" << endl;
        return 0;
    }
    if(N == 5){
        cout << 7 << endl;
        cout << "1 2 1" << endl;
        cout << "2 3 3" << endl;
        cout << "3 4 5" << endl;
        cout << "4 5 7" << endl;
        cout << "2 3 4" << endl;
        cout << "3 4 9" << endl;
        cout << "4 5 16" << endl;
        cout << "1 1" << endl;
        cout << "2 1 2" << endl;
        cout << "3 1 2 3" << endl;
        cout << "4 1 2 3 4" << endl;
        cout << "1 5" << endl;
        cout << "2 5 3" << endl;
        cout << "3 5 3 4" << endl;
        cout << "1 6" << endl;
        cout << "2 6 4" << endl;
        cout << "3 7" << endl;
        return 0;
    }
}

    vector<bool> Sq(40000);
    for(int i=1; i<200; i++) Sq.at(i*i) = true;
    if(N <= 11){
        return 0;
        while(true){
            vector<int> A(N),B(N);
            vector<bool> already(201);
            for(int p=0; p<N-3; p+=4){
                for(int i=0; i<4; i++){
                    if(i+p == N-3) break;
                    for(int v=1; ; v++) if(!already.at(v) && !already.at(v+(1<<i))){
                        already.at(v) = true,already.at(v+(1<<i)) = true;
                        A.at(i+p) = v,B.at(i+p) = v+(1<<i); break;
                    }
                }
            }
            for(int i=N-3; i<N; i++) for(int v=1; ; v++) if(!already.at(v)){
                already.at(v) = true,A.at(i) = v,B.at(i) = v;
                break;
            }
            for(int i=0; i<N-3; i++) if(A.at(i) > B.at(i)) swap(A.at(i),B.at(i));

            bool ok = true;
            vector<vector<pair<int,int>>> S(N,vector<pair<int,int>>(N));
            for(int i=0; i<N&&ok; i++){
                for(int k=i+1; k<N; k++){
                    vector<int> Bs(200,-1);
                    Bs.at(0) = 0;
                    int sum = 0;
                    for(int p=i; p!=k; p++){
                        sum += A.at(p);
                        if(A.at(p) == B.at(p)) continue;
                        int d = B.at(p)-A.at(p);
                        for(int v=199; v>=d; v--) if(Bs.at(v-d) != -1) Bs.at(v) = Bs.at(v-d)+(1<<p);
                    }
                    bool end = true;
                    for(int v=0; v<200; v++) if(Bs.at(v) != -1 && Sq.at(sum+v)){
                        end = false;
                        S.at(i).at(k) = {1,Bs.at(v)};
                        break;
                    }
                    if(!end) continue;
                    Bs.assign(200,-1);
                    sum = 0,Bs.at(0) = 0;
                    for(int p=(i-1+N)%N; ; p=(p-1+N)%N){
                        sum += A.at(p);
                        if(A.at(p) != B.at(p)){
                            int d = B.at(p)-A.at(p);
                            for(int v=199; v>=d; v--) if(Bs.at(v-d) != -1) Bs.at(v) = Bs.at(v-d)+(1<<p);
                        }
                        if(p == k) break;
                    }
                    for(int v=0; v<200; v++) if(Bs.at(v) != -1 && Sq.at(sum+v)){
                        end = false;
                        S.at(i).at(k) = {0,Bs.at(v)};
                        break;
                    }
                    if(end){ok = false; break;}
                }

            }   
            if(!ok) continue;
            cout << 2*N-3 << "\n";
            for(int i=0; i<N; i++) cout << i+1 << " " << (i+1)%N+1 << " " << A.at(i) << "\n";
            for(int i=0; i<N-3; i++) cout << i+1 << " " << i+2 << " " << B.at(i) << "\n";
            for(int i=0; i<N; i++) for(int k=i+1; k<N; k++){
                auto [inc,s] = S.at(i).at(k);
                vector<int> P;
                if(inc){
                    for(int p=i; p!=k; p++){
                        if(s&(1<<p)) P.push_back(N+p);
                        else P.push_back(p); 
                    }
                }
                else{
                    for(int p=(i-1+N)%N; ; p=(p-1+N)%N){
                        if(s&(1<<p)) P.push_back(N+p);
                        else P.push_back(p);
                        if(p == k) break;
                    }
                }
                int now = 0;
                cout << P.size();
                for(auto p : P){
                    if(p < N) now += A.at(p);
                    else now += B.at(p-N);
                    cout << " " << p+1;
                }    
                cout << "\n";
                if(!Sq.at(now)){cout << "Wrong" << endl; return 0;}
            }
            break;
        }
    }
    else if(N <= 20){
        while(true){
            vector<int> A(N),B(N);
            vector<bool> already(201);
            for(int p=0; p<N-3; p+=6){
                for(int i=0; i<6; i++){
                    if(i+p == N-3) break;
                    for(int v=1; ; v++) if(!already.at(v) && !already.at(v+(1<<i))){
                        already.at(v) = true,already.at(v+(1<<i)) = true;
                        A.at(i+p) = v,B.at(i+p) = v+(1<<i); break;
                    }
                }
            }
            for(int i=N-3; i<N; i++) for(int v=1; ; v++) if(!already.at(v)){
                already.at(v) = true,A.at(i) = v,B.at(i) = v;
                break;
            }
            for(int i=0; i<N-3; i++) if(A.at(i) > B.at(i)) swap(A.at(i),B.at(i));

            bool ok = true;
            vector<vector<pair<int,int>>> S(N,vector<pair<int,int>>(N));
            for(int i=0; i<N&&ok; i++){
                for(int k=i+1; k<N; k++){
                    vector<int> Bs(200,-1);
                    Bs.at(0) = 0;
                    int sum = 0;
                    for(int p=i; p!=k; p++){
                        sum += A.at(p);
                        if(A.at(p) == B.at(p)) continue;
                        int d = B.at(p)-A.at(p);
                        for(int v=199; v>=d; v--) if(Bs.at(v-d) != -1) Bs.at(v) = Bs.at(v-d)+(1<<p);
                    }
                    bool end = true;
                    for(int v=0; v<200; v++) if(Bs.at(v) != -1 && Sq.at(sum+v)){
                        end = false;
                        S.at(i).at(k) = {1,Bs.at(v)};
                        break;
                    }
                    if(!end) continue;
                    Bs.assign(200,-1);
                    sum = 0,Bs.at(0) = 0;
                    for(int p=(i-1+N)%N; ; p=(p-1+N)%N){
                        sum += A.at(p);
                        if(A.at(p) != B.at(p)){
                            int d = B.at(p)-A.at(p);
                            for(int v=199; v>=d; v--) if(Bs.at(v-d) != -1) Bs.at(v) = Bs.at(v-d)+(1<<p);
                        }
                        if(p == k) break;
                    }
                    for(int v=0; v<200; v++) if(Bs.at(v) != -1 && Sq.at(sum+v)){
                        end = false;
                        S.at(i).at(k) = {0,Bs.at(v)};
                        break;
                    }
                    if(end){ok = false; break;}
                }

            }   
            if(!ok) continue;
            cout << 2*N-3 << "\n";
            for(int i=0; i<N; i++) cout << i+1 << " " << (i+1)%N+1 << " " << A.at(i) << "\n";
            for(int i=0; i<N-3; i++) cout << i+1 << " " << i+2 << " " << B.at(i) << "\n";
            for(int i=0; i<N; i++) for(int k=i+1; k<N; k++){
                auto [inc,s] = S.at(i).at(k);
                vector<int> P;
                if(inc){
                    for(int p=i; p!=k; p++){
                        if(s&(1<<p)) P.push_back(N+p);
                        else P.push_back(p); 
                    }
                }
                else{
                    for(int p=(i-1+N)%N; ; p=(p-1+N)%N){
                        if(s&(1<<p)) P.push_back(N+p);
                        else P.push_back(p);
                        if(p == k) break;
                    }
                }
                int now = 0;
                cout << P.size();
                for(auto p : P){
                    if(p < N) now += A.at(p);
                    else now += B.at(p-N);
                    cout << " " << p+1;
                }    
                cout << "\n";
                if(!Sq.at(now)){cout << "Wrong" << endl; return 0;}
            }
            break;
        }
    }
    else{
        while(true){
            vector<int> A(N),B(N);
            vector<bool> already(201);
            for(int i=0; i<6; i++){
                for(int v=1; ; v++) if(!already.at(v) && !already.at(v+(1<<i))){
                    already.at(v) = true,already.at(v+(1<<i)) = true;
                    A.at(i) = v,B.at(i) = v+(1<<i); break;
                }
            }
            for(int i=0; i<6; i++){
                for(int v=1; ; v++) if(!already.at(v) && !already.at(v+(1<<i))){
                    already.at(v) = true,already.at(v+(1<<i)) = true;
                    A.at(i+6) = v,B.at(i+6) = v+(1<<i); break;
                }
            }
            for(int i=0; i<min(N-15,50); i++){
                for(int v=100; ; v++) if(!already.at(v) && !already.at(v+50)){
                    already.at(v) = true,already.at(v+50) = true;
                    A.at(i+12) = v,B.at(i+12) = v+50; break;
                }
            }
            for(int i=0; i<N; i++) if(A.at(i) == 0) for(int v=1; v<=200; v++) if(!already.at(v)){
                already.at(v) = true,A.at(i) = v; break;
            }
            for(int i=0; i<N-3; i++) if(B.at(i) == 0) for(int v=1; v<=200; v++) if(!already.at(v)){
                already.at(v) = true,B.at(i) = v; break;
            }
            B.at(N-3) = A.at(N-3),B.at(N-2) = A.at(N-2),B.at(N-1) = A.at(N-1);
            
            for(int i=0; i<N-3; i++) if(A.at(i) > B.at(i)) swap(A.at(i),B.at(i));

            bool ok = true;
            vector<vector<vector<int>>> S(N,vector<vector<int>>(N));
            int time = 0;
            vector<int> T(N,-1);
            for(int i=0; i<N&&ok; i++){
                for(int k=i+1; k<N; k++,time++){
                    vector<int> Bs(200,-1);
                    Bs.at(0) = 0;
                    int sum = 0;
                    for(int p=i; p!=k; p++){
                        sum += A.at(p);
                        if(A.at(p) == B.at(p)) continue;
                        int d = B.at(p)-A.at(p);
                        for(int v=199; v>=d; v--) if(Bs.at(v-d) != -1 && Bs.at(v) == -1) Bs.at(v) = p;
                    }
                    bool end = true;
                    for(int v=0; v<200; v++) if(Bs.at(v) != -1 && Sq.at(sum+v)){
                        end = false;
                        while(v){
                            int p = Bs.at(v);
                            T.at(p) = time;
                            v -= B.at(p)-A.at(p);
                        }
                        vector<int> now;
                        for(int p=i; p!=k; p++){
                            if(T.at(p) == time) now.push_back(N+p);
                            else now.push_back(p);
                        }
                        S.at(i).at(k) = now;
                        break;
                    }
                    if(!end) continue;
                    Bs.assign(200,-1);
                    sum = 0,Bs.at(0) = 0;
                    for(int p=(i-1+N)%N; ; p=(p-1+N)%N){
                        sum += A.at(p);
                        if(A.at(p) != B.at(p)){
                            int d = B.at(p)-A.at(p);
                            for(int v=199; v>=d; v--) if(Bs.at(v-d) != -1 && Bs.at(v) == -1) Bs.at(v) = p;
                        }
                        if(p == k) break;
                    }
                    for(int v=0; v<200; v++) if(Bs.at(v) != -1 && Sq.at(sum+v)){
                        end = false;
                        while(v){
                            int p = Bs.at(v);
                            T.at(p) = time;
                            v -= B.at(p)-A.at(p);
                        }
                        vector<int> now;
                        for(int p=(i-1+N)%N; ; p=(p-1+N)%N){
                            if(T.at(p) == time) now.push_back(N+p);
                            else now.push_back(p);
                            if(p == k) break;
                        }
                        S.at(i).at(k) = now;
                        break;
                    }
                    if(end){ok = false; break;}
                }

            }   
            if(!ok) continue;
            cout << 2*N-3 << "\n";
            for(int i=0; i<N; i++) cout << i+1 << " " << (i+1)%N+1 << " " << A.at(i) << "\n";
            for(int i=0; i<N-3; i++) cout << i+1 << " " << i+2 << " " << B.at(i) << "\n";
            for(int i=0; i<N; i++) for(int k=i+1; k<N; k++){
                auto P = S.at(i).at(k);
                int now = 0;
                cout << P.size();
                for(auto p : P){
                    if(p < N) now += A.at(p);
                    else now += B.at(p-N);
                    cout << " " << p+1;
                }    
                cout << "\n";
                if(!Sq.at(now)){cout << "Wrong" << endl; return 0;}
            }
            break;
        }
    }
}
0