Please help with this question backtracking

Revision en2, by om1429888, 2022-07-16 21:46:38

https://www.spoj.com/problems/BTCK/


#include<iostream> #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ll long long #define pb push_back #define fast_io ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fr(i,a,b) for(int i=a;i<b;i++) #define loop(x,n) for(int x=0;x<n;x++) #define mod 1e7 #define inf (1LL<<60) #define all(x) (x).begin(),(x).end() #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> void precal(){ } vector<int>perm={0,1,2,3,4,5,6,7,8,9}; vector<ll>input(10); bool helper(ll k,ll index,ll sum){ if(sum>k)return false; if(index==10){ fr(i,0,10){ cout<<perm[i]<<" "; } cout<<endl; return true; } for(int i=index;i<10;i++){ swap(perm[index],perm[i]); bool check=helper(k,index+1,sum+input[index]*perm[index]); if(check){ swap(perm[index],perm[i]); return true; } swap(perm[index],perm[i]); } return false; } void solve(){ fr(i,0,10)cin>>input[i]; ll k; cin>>k; bool check=helper(k,0,0); if(!check){ cout<<-1<<endl; } } int main() { fast_io; cout<<fixed; cout<<setprecision(10); precal(); int t=1;cin>>t; for(int i=1;i<=t;i++) { //cout<<Case #<<i<<: ; solve(); } return 0; }

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English om1429888 2022-07-16 21:46:38 54
en1 English om1429888 2022-07-16 21:46:09 1489 here im trying to swap to generate permuations that are lexicographically smaller but this code is giving wrong answer (published)