fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. vector<vector<int>> paths[205];
  6.  
  7. void Solve() {
  8.   int i, j, k;
  9.   int n, m;
  10.  
  11.   cin >> n >> m;
  12.   assert(4<=n && n<=100000);
  13.   assert(20<=m && m<=200);
  14.   vector<int> cost(n);
  15.   for (i = 0; i < n; ++i) {
  16.     cin >> cost[i];
  17.     assert(0<=cost[i] && cost[i]<=1e9);
  18.   }
  19.  
  20.   vector<int> nodes;
  21.   int ans = -1;
  22.   for (i = 1; i < n; ++i) nodes.push_back(i);
  23.  
  24.   do {
  25.     ll path_cost = (cost[0]^cost[nodes[0]]) + (cost[0]^cost[nodes.back()]);
  26.     for (i = 1; i < nodes.size(); ++i) path_cost += cost[nodes[i]]^cost[nodes[i-1]];
  27.     path_cost %= m;
  28.     paths[path_cost].push_back(nodes);
  29.     if (paths[path_cost].size()>2) {
  30.       ans = path_cost;
  31.       break;
  32.     }
  33.   } while (next_permutation(nodes.begin(), nodes.end()));
  34.  
  35.   if (ans == -1) {
  36.     cout << "No" << endl;
  37.   } else {
  38.     cout << "YES" << endl;
  39.     for (i = 0; i < 3; ++i) {
  40.       cout << 1;
  41.       for (j = 0; j < paths[ans][i].size(); ++j) {
  42.         cout << " " << paths[ans][i][j]+1;
  43.       }
  44.       cout << " " << 1 << endl;
  45.     }
  46.   }
  47.  
  48.   for (i = 0; i < m; ++i) paths[i].clear();
  49. }
  50.  
  51. int main() {
  52.   int t;
  53.   cin >> t;
  54.   assert(1<=t && t<=25000);
  55.   while (t--) Solve();
  56. }
  57.  
Success #stdin #stdout 0s 5688KB
comments (?)
stdin
copy 
2
4 20
0 1 1 0
4 30
5 3 1 7
stdout
copy 
YES
1 2 3 4 1
1 3 2 4 1
1 4 2 3 1
No
https://ideone.com/A5Q6dh
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!