#1159228 (C++17) No.3506 All Distance is Square Number

• 問題: No.3506 All Distance is Square Number
• ユーザー: GOTKAKO
• 提出日時: 2026-04-18 06:33:49
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,050 bytes
• コンパイル時間: 1,677 ms
• コンパイル使用メモリ: 234,732 KB
• 実行使用メモリ: 7,976 KB
• 最終ジャッジ日時: 2026-04-18 06:34:05
• 合計ジャッジ時間: 8,562 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
other	AC * 3 WA * 26

ソースコード

#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 <= 100){
        while(true){
            vector<int> W(N*3+9);
            iota(W.begin(),W.end(),1);
            vector<int> A(N),B(N);
            shuffle(W.begin(),W.end(),mt);
            for(int i=0; i<N; i++) A.at(i) = W.at(i);
            for(int i=0; i<N-3; i++) B.at(i) = W.at(i+N);
            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<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(1000,-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=999; 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<1000; 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(1000,-1);
                    sum = 0,Bs.at(0) = 0;
                    for(int p=(i-1+N)%N; p!=k; p=(p-1+N)%N){
                        sum += A.at(p);
                        if(A.at(p) == B.at(p)) continue;
                        int d = B.at(p)-A.at(p);
                        for(int v=999; v>=d; v--) if(Bs.at(v-d) != -1) Bs.at(v) = Bs.at(v-d)+(1<<p);
                    }
                    for(int v=0; v<1000; 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!=k; p=(p-1+N)%N){
                        if(s&(1<<p)) P.push_back(N+p);
                        else P.push_back(p);
                    }
                }
                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{

    }
}