結果
| 問題 | No.3506 All Distance is Square Number |
| コンテスト | |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2026-04-18 07:40:13 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 14,023 bytes |
| 記録 | |
| コンパイル時間 | 3,411 ms |
| コンパイル使用メモリ | 259,688 KB |
| 実行使用メモリ | 16,192 KB |
| 最終ジャッジ日時 | 2026-04-18 07:40:38 |
| 合計ジャッジ時間 | 6,446 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 WA * 1 TLE * 1 -- * 24 |
ソースコード
#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){
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;
}
}
}