QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625780#9426. Relearn through ReviewWaO_oWA 191ms5892kbC++202.9kb2024-10-09 21:00:532024-10-09 21:00:53

Judging History

你现在查看的是最新测评结果

  • [2024-10-09 21:00:53]
  • 评测
  • 测评结果:WA
  • 用时:191ms
  • 内存:5892kb
  • [2024-10-09 21:00:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int __int128
#define deg( x ) cerr<<""#x"="<<x<<endl
//#define endl '\n'

istream &operator>>( istream &in , __int128 &n ){
    string s; in>>s;
    n=0;

    for(char i:s) n=n*10+i-'0';

    return in;
}

ostream &operator<<( ostream &out , __int128 n ){
    if( n==0 ){
        out<<0;
        return out;
    }

    string s;

    while( n ){
        s+='0'+n%10;
        n/=10;
    }
    reverse( s.begin( ) , s.end( ) );
    out<<s;
    return out;
}

const int N=3e5+10;

int idn=0;
int fan[ N ];

int A[ N ];

int gcd( int a , int b ){
    if( b==0 ) return a;
    return gcd( b , a%b );
}

void solve(){
    int n,k;
    cin>>n>>k;

    for( int i=1; i<=n; i++ ){
        cin>>A[ i ];
    }

    int ans=0;
/*
//    vector<int> V;
//    V.emplace_back( 0 );
//
//    int e=1;
//    while( e<=n ){
//        int te=A[ e ];
//        while( A[ e ]==te ){
//            e++;
//            if( e==n+1 ) break;
//        }
//        V.emplace_back( te );
//    }
//
//    n=V.size()-1;
//    for( int l=1; l<=min( n , 1ll+50 ); l++ ){
//        cnt=0;
//        for( int o=1; o<l; o++ ) cnt=gcd( cnt , V[ o ] );
//        for( int r=max( l+1 , n-50 ); r<=n; r++ ){
//            int te=cnt;
//            for( int o=l; o<=r; o++ ){
//                te=gcd( te , V[ o ]+k );
//            }
//            for( int o=r+1; o<=n; o++ ) te=gcd( te , V[ o ] );
//
//            ans=max( ans , te );
//        }
//    }
 */

    vector<int> V;
    int oo=0;
    for( int i=1; i<=n; i++ ){
        oo=gcd( oo , A[ i ] );
        V.emplace_back( oo );
    }

    oo=0;
    for( int i=n; i>=1; i-- ){
        oo=gcd( oo , A[ i ] );
        V.emplace_back( oo );
    }

    oo=0;
    for( int i=n; i>=1; i-- ){
        oo=gcd( oo , A[ i ]+k );
        V.emplace_back( oo );
    }

    oo=0;
    for( int i=1; i<=n; i++ ){
        oo=gcd( oo , A[ i ]+k );
        V.emplace_back( oo );
    }

    sort( V.begin() , V.end() );
    V.erase( unique( V.begin() ,  V.end() ) ,  V.end() );

    idn=0;
    for( auto x:V ){
        fan[ ++idn ]=x;
    }

    for( int i=idn; i>=1; i-- ){
        int now=fan[ i ];
        if( now <= ans ) break;
        if( now==0 ) continue;

        bool ok=false;

        int l=1;
        for( ; l<=n; l++ ){
            if( A[ l ]%now != 0 ) break;
        }

        int r=n;
        for( ; r>=1; r-- ){
            if( A[ r ]%now != 0 ) break;
        }

        for( int e=l; e<=r; e++ ){
            if( ( A[ e ]+k )%now!=0 ){
                ok=true;
                break;
            }
        }

        if( ok ) continue;

        ans=max( ans , now );
    }

    cout<<ans<<endl;

}

signed main() {
    ios::sync_with_stdio( 0 );
    cin.tie( 0 ); cout.tie( 0 );

    int T=1;
    cin>>T;

    while( T-- ){
        solve();
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5892kb

input:

2
6 2
5 3 13 8 10 555
3 0
3 6 9

output:

5
3

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 191ms
memory: 5712kb

input:

100000
1 608611451460421713
33155506392034032
1 743116173559300609
6138108577573005
7 364454564010802125
657035115675878115 657035115675878115 657035115675878115 657035115675878115 657035115675878115 292580551665075990 657035115675878115
4 316648374341335221
365788422120542814 182894211060271407 731...

output:

641766957852455745
749254282136873614
657035115675878115
182894211060271407
880411769063535667
560553564512176618
183698346865682381
962990836390050009
616597869896951268
878097339332572161
188820994675344528
997057718507559252
949074379610491450
2
632093288650732211
377121713907330928
3565025466088...

result:

wrong answer 14th lines differ - expected: '37337367838628559', found: '2'