yicongli

Gym 101848E

Jan 23rd, 2021
820
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=40000;
  17.  
  18. int n,p;
  19. bool vis[N];
  20. bool F[N];
  21. int a[1005];
  22. int b[505];
  23.  
  24. bool f(int x){
  25.     if(x<=0)return !x;
  26.     if(vis[x])return F[x];
  27.     vis[x]=1;
  28.     for(int i=1;i<=(n<<1);++i){
  29.         F[x]|=f(x-a[i]);
  30.     }
  31.     return F[x];
  32. }
  33.  
  34. int main(){
  35.     // freopen(".in","r",stdin);
  36.     // freopen(".out","w",stdout);
  37.     r(n),r(p);
  38.     for(int i=1;i<=(n<<1);++i)r(a[i]);
  39.     while(p){
  40.         int c=0,s=0;
  41.         if(!f(p))p+=100,c=1;
  42.         for(int i=1;i<=n;++i)r(b[i]);
  43.         for(int i=1;i<=n;++i){
  44.             if(f(p-a[b[i]])){
  45.                 s=b[i];
  46.                 p-=a[b[i]];
  47.                 break;
  48.             }
  49.         }
  50.         printf("%d %d\n",c,s);
  51.         fflush(stdout);
  52.     }
  53.     return 0;
  54. }
RAW Paste Data