fork download
copy 
  1. //author - techaddict
  2. #include <iostream>
  3. #include <sstream>
  4. #include <string>
  5. #include <vector>
  6. #include <deque>
  7. #include <queue>
  8. #include <set>
  9. #include <map>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <utility>
  13. #include <cmath>
  14. #include <cstring>
  15. #include <cstdlib>
  16. #include <ctime>
  17. #include <cstdio>
  18. using namespace std;
  19.  
  20. #define ap cout<<"AP=";for(ull i=1;i<=n;i++)if(AP[i])cout<<a[i]<<" ";cout<<endl;
  21. #define gp cout<<"GP=";for(ull i=1;i<=n;i++)if(GP[i])cout<<a[i]<<" ";cout<<endl;
  22. typedef long long ull ;
  23. typedef struct{
  24.     ull num,den;
  25. }ratio;
  26. const double EPS = 1e-9;
  27. ull M,n;
  28. ull a[10010];
  29. bool AP[10010];
  30. bool GP[10010];
  31. ull ind[100010];
  32.  
  33. inline ull  GetInt(){
  34.     char c;
  35.     while(c=getchar(),c<'0'||c>'9');
  36.     ull X=0;
  37.     while(c>='0'&&c<='9'){
  38.         X=X*10+c-48;
  39.         c=getchar();
  40.     }
  41.     return X;
  42. }
  43.  
  44. inline void PutInt(ull X){
  45.     ull Len=0,Data[10];
  46.     while(X){
  47.         Data[Len++]=X%10;
  48.         X/=10;
  49.     }
  50.     while(Len--)
  51.         putchar(Data[Len]+48);
  52. }
  53.  
  54. bool solve(ull i, ull j) {
  55.    ull x = (int)(pow((double)i, 1. / j) + EPS);
  56.    return (int)(pow((double)x, j) + EPS) == i;
  57. }
  58.  
  59. ratio simplify(ull num, ull den){
  60.     ull gcd=__gcd(num,den);
  61.     ratio a={num/gcd,den/gcd};
  62.     return a;
  63. }
  64.  
  65. void mark_ap(ull a1, ull d){
  66.     memset(AP,0,sizeof(AP));
  67.     AP[ind[a1]]=1;
  68.     ull next=a1+d;
  69.     while(next<=M&&ind[next]){
  70.         AP[ind[next]]=1;
  71.         next=next+d;
  72.     }
  73. }
  74.  
  75. void mark_gp(ull a1, ratio r){
  76.     memset(GP,0,sizeof(GP));
  77.     GP[ind[a1]]=1;
  78.     ratio f=simplify(r.num*a1,r.den);
  79.     while(f.num<=M*f.den&&f.den==1){
  80.         GP[ind[f.num]]=1;
  81.         f=simplify(f.num*r.num, f.den*r.den);
  82.     }
  83. }
  84.  
  85. bool checkall(){
  86.     ull cnt=1;
  87.     for(ull i=1;i<=n;i++){
  88.         if(!AP[i]&&!GP[i]){
  89.             cnt=0;
  90.             break;
  91.         }
  92.     }
  93.     if(cnt){
  94.         for(ull i=1;i<=n;i++){
  95.             if(AP[i]){
  96.                 PutInt(a[i]);putchar(' ');
  97.             }
  98.         }
  99.         putchar('\n');
  100.         for(ull i=1;i<=n;i++){
  101.             if(GP[i]){
  102.                 PutInt(a[i]);putchar(' ');
  103.             }
  104.         }
  105.         putchar('\n');
  106.         return true;
  107.     }
  108.     return false;
  109. }
  110.  
  111. bool check1(ull a1, ull a2){
  112.     mark_ap(a1,a2-a1);
  113.     ull A=-1,B=-1;bool cnt=0;
  114.     for(ull i=1;i<=n;i++){
  115.         if(!AP[i]&&cnt==0)A=a[i],cnt=1;
  116.         else if(!AP[i]&&cnt==1){
  117.             B=a[i];break;
  118.         }
  119.     }
  120.     if(A==-1||B==-1)return false;
  121.     for(ull k=1;k<=16;k++){
  122.         if(solve(B,k)&&solve(A,k)){
  123.             ratio r=simplify((int)pow(B,1.0/k),(int)pow(A,1.0/k));
  124.             mark_gp(A, r);
  125.             if(checkall())return true; 
  126.         }
  127.     }
  128.     return false;   
  129. }
  130.  
  131. bool check2(ull a1, ull a2){
  132.     ratio r=simplify(a2,a1);
  133.     mark_gp(a1,r);
  134.     ull A=-1,B=-1;bool cnt=0;
  135.     for(ull i=1;i<=n;i++){
  136.         if(!GP[i]&&cnt==0)A=a[i],cnt=1;
  137.         else if(!GP[i]&&cnt==1){
  138.             B=a[i];break;
  139.         }
  140.     }
  141.     if(A==-1||B==-1)return false;
  142.     for(ull k=1;k<=3;k++){
  143.         ull diff=(B-A)/k;
  144.         if(diff==0)return false;
  145.         mark_ap(A,diff);
  146.         if(checkall())return true; 
  147.     }
  148.     return false;
  149. }
  150.  
  151. int main(){
  152.     #ifndef ONLINE_JUDGE
  153.         freopen("input.txt", "r", stdin);
  154.         freopen("output.txt", "w", stdout);
  155.     #endif
  156.     ull t,b,c,d,m,x,y;
  157.     t=GetInt();
  158.     while(t--){
  159.         memset(ind,0,sizeof(ind));
  160.         n=GetInt();
  161.         for(ull pos=1;pos<=n;pos++){
  162.             a[pos]=GetInt();
  163.             ind[a[pos]]=pos;
  164.         }
  165.         M=a[n];
  166.         if(n==2){
  167.             for(ull i=1;i<=2;i++){
  168.                 PutInt(a[i]);putchar(' ');
  169.             }
  170.             putchar('\n');
  171.             for(ull i=1;i<=2;i++){
  172.                 PutInt(a[i]);putchar(' ');
  173.             }
  174.             putchar('\n');
  175.         }
  176.         else if(n==3){
  177.             for(ull i=1;i<=2;i++){
  178.                 PutInt(a[i]);putchar(' ');
  179.             }
  180.             putchar('\n');
  181.             for(ull i=2;i<=3;i++){
  182.                 PutInt(a[i]);putchar(' ');
  183.             }
  184.             putchar('\n');
  185.         }
  186.         else if(check1(a[1],a[2])){
  187.             //cout<<"case1"<<endl;
  188.         }
  189.         else if(check1(a[1],a[3])){
  190.             //cout<<"case2"<<endl;
  191.         }
  192.         else if(check1(a[2],a[3])){
  193.             //cout<<"case3"<<endl;
  194.         }
  195.         else if(check2(a[1],a[2])){
  196.             //cout<<"case4"<<endl;
  197.         }
  198.         else if(check2(a[1],a[3])){
  199.             //cout<<"case5"<<endl;
  200.         }
  201.         else if(check2(a[2],a[3])){
  202.             //cout<<"case6"<<endl;
  203.         }
  204.     }
  205. }
Success #stdin #stdout 0.01s 3564KB
comments (?)
stdin
copy 
4
6
2 4 5 8 11 16
5
1 2 3 4 5
8
1 3 9 10 19 27 28 81
6
1 4 7 10 13 25
stdout
copy 
2 5 8 11 
4 16 
1 3 5 
2 4 
10 19 28 
1 3 9 27 81 
1 7 13 
4 10 25
https://ideone.com/Ma5ws1
language:
C++ (gcc 8.3)
created:
11 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!