Advertisement
Guest User

Untitled

a guest
Jun 1st, 2013
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.14 KB | None | 0 0
  1. //#include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <cstring>
  7. #include <string>
  8. #include <cmath>
  9. #include <cassert>
  10. #include <ctime>
  11. #include <algorithm>
  12. #include <sstream>
  13. #include <list>
  14. #include <queue>
  15. #include <deque>
  16. #include <stack>
  17. #include <cstdlib>
  18. #include <cstdio>
  19. #include <iterator>
  20. #include <functional>
  21. #include <bitset>
  22. #define mp make_pair
  23. #define pb push_back
  24.  
  25. #ifdef LOCAL
  26. #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  27. #else
  28. #define eprintf(...)
  29. #endif
  30.  
  31. #define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", clock()*1.0/CLOCKS_PER_SEC)
  32. #define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, clock()*1.0/CLOCKS_PER_SEC)
  33.  
  34. #if ( _WIN32 || __WIN32__ )
  35.     #define LLD "%I64d"
  36. #else
  37.     #define LLD "%lld"
  38. #endif
  39.  
  40. using namespace std;
  41.  
  42. #define TASKNAME "C"
  43. #define TASKMOD "large"
  44.  
  45. typedef long long ll;
  46. typedef long double ld;
  47.  
  48. void PreCalc(){
  49. }
  50.  
  51. int na[2100];
  52. int nb[2100];
  53. int a[2100];
  54. int b[2100];
  55.  
  56. int ans[2100];
  57. //bool used[2100];
  58. int n;
  59.  
  60. void _myassert(bool q,string s){
  61.     if (q) return;
  62.     for (int k = 0; k < n; k++)
  63.         eprintf("%2d%c",ans[k]," \n"[k==n-1]);
  64.     for (int k = 0; k < n; k++)
  65.         eprintf("%2d%c",a[k]," \n"[k==n-1]);
  66.     for (int k = 0; k < n; k++)
  67.         eprintf("%2d%c",b[k]," \n"[k==n-1]);
  68.     eprintf("\n");
  69.     for (int k = 0; k < n; k++)
  70.         eprintf("%2d%c",na[k]," \n"[k==n-1]);
  71.     for (int k = 0; k < n; k++)
  72.        eprintf("%2d%c",nb[k]," \n"[k==n-1]);
  73.     eprintf("%s\n",s.data());
  74.     assert(false);
  75. }
  76.  
  77. #define myassert(x) _myassert(x,#x)
  78.  
  79. void solve(){
  80.     scanf("%d",&n);
  81.     for (int i = 0; i < n; i++)
  82.         scanf("%d",&na[i]);
  83.     for (int i = 0; i < n; i++)
  84.         scanf("%d",&nb[i]);
  85.  
  86.     for (int i = 0; i < n; i++)
  87.         ans[i] = -1;
  88.  
  89.     for (int i = 0; i < n; i++)
  90.         a[i] = b[i] = 1;
  91.  
  92.     for (int i = 0; i < n; i++){
  93.         for (int j = 0; j <= n; j++){
  94.             myassert (j != n);         
  95.             if (ans[j] != -1) continue;
  96. //          eprintf("!!%d %d %d %d %d\n",j,a[j],na[j],b[j],nb[j]);
  97.             if (a[j] == na[j] && b[j] == nb[j]){
  98.                 bool ok = true;
  99.                 for (int k = 0; k < n && ok; k++) {
  100.                     ok &= (ans[k] != -1 || ((a[j]+1)*(k > j) <= na[k] && (b[j]+1)*(k < j) <= nb[k]));
  101.                 }
  102.                 if (!ok) continue;
  103.                 ans[j] = i;
  104. //              used[j] = true;
  105.                 for (int k = 0; k < j; k++){
  106.                     if (ans[k] == -1)
  107.                         b[k] = max(b[k],b[j]+1);
  108.                 }  
  109.                 for (int k = j+1; k < n; k++){
  110.                     if (ans[k] == -1)
  111.                         a[k] = max(a[k],a[j]+1);
  112.                 }
  113.                 for (int k = 0; k < n; k++)
  114.                     myassert(ans[k] != -1 || (a[k] <= na[k] && b[k] <= nb[k]));
  115.                 break;
  116.             }
  117.         }
  118.     }
  119.  
  120.     for (int i = 0; i < n; i++)
  121.         printf("%d%c",ans[i]+1," \n"[i==n-1]);
  122. }
  123.  
  124.  
  125. int main(){
  126.   freopen(TASKNAME"-"TASKMOD".in","r",stdin);
  127.   freopen(TASKNAME"-"TASKMOD".out","w",stdout);
  128.    
  129.   PreCalc();   
  130.   TIMESTAMP(PreCalc);
  131.  
  132.   char buf[1000];
  133.   int testNum;
  134.   gets(buf);
  135.   sscanf(buf,"%d",&testNum);
  136.  
  137.   for (int testId = 1; testId <= testNum; testId++){
  138.     if (testId <= 20 || testId >= testNum - 20 || testId % 10 == 0)
  139.         TIMESTAMPf("Test %d",testId);
  140.     printf("Case #%d: ",testId);
  141.     solve();                        
  142.   }
  143.      
  144.   TIMESTAMP(end);
  145.   return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement