QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#627679#7747. Memory53DawnsTL 14ms5152kbC++231.7kb2024-10-10 16:44:222024-10-10 16:44:24

Judging History

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

  • [2024-10-10 16:44:24]
  • 评测
  • 测评结果:TL
  • 用时:14ms
  • 内存:5152kb
  • [2024-10-10 16:44:22]
  • 提交

answer


#include <bits/stdc++.h>
#pragma GCC optimize (1)
#pragma GCC optimize (2)
#pragma GCC optimize (3)
// #define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0)

using namespace std;

const int N=1e6+10,M=1e6+10,mod=1e9+7;

void sol(int cases) {
    int n;
    cin>>n;

    vector<int>a(n+1);

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

    vector<int>pre1(2*n+100),pre2(2*n+100);

    int maxn1=0,maxn2=0;

    for(int i=1;i<=n;++i){
        int f=1;
        if(a[i]<0) f=-1;
        int x=abs(a[i]);
        for(int j=0;j<=30;++j){
            if(x>>j&1){
                if(f==1){
                    pre1[i+j]++;
                    int w=i+j;
                    while(pre1[w]>=2){
                        pre1[w+1]+=pre1[w]/2;
                        pre1[w]%=2;
                        w++;
                    }
                    maxn1=max(maxn1,w);
                }else{
                    pre2[i+j]++;
                    int w=i+j;
                    while(pre2[w]>=2){
                        pre2[w+1]+=pre2[w]/2;
                        pre2[w]%=2;
                        w++;
                    }
                    maxn2=max(maxn2,w);               
                }
            }
        }


        int w=max(maxn1,maxn2);
        // cout<<maxn1<<' '<<maxn2<<' '<<w<<'\n';
        // return;
        while(w>=0){
            if(pre1[w]==pre2[w]) w--;
            else break;
        }
        if(w==-1) cout<<0;
        else if(pre1[w]==1) cout<<"+";
        else cout<<"-";

    }




}

signed main(){
     IOS;
    int t=1;
    // cin>>t;
    for(int i=1;i<=t;++i){
        sol(i);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3560kb

input:

10
2 -1 4 -7 4 -8 3 -6 4 -7

output:

+0+-+---+-

result:

ok single line: '+0+-+---+-'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

10
-1 36 18 18 18 18 18 18 18 -18

output:

-++++++++-

result:

ok single line: '-++++++++-'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3676kb

input:

1000
-1 193552 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 96776 967...

output:

-+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

result:

ok single line: '-+++++++++++++++++++++++++++++...++++++++++++++++++++++++++++++-'

Test #4:

score: 0
Accepted
time: 14ms
memory: 5152kb

input:

100000
-1 696082628 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 348041314 ...

output:

-+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...

result:

ok single line: '-+++++++++++++++++++++++++++++...++++++++++++++++++++++++++++++-'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10
-1 70 -35 -72 36 12 -6 42 -21 -84

output:

-+---+-+--

result:

ok single line: '-+---+-+--'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

1000
-1 -120742 60371 -567374 283687 -507718 253859 -579246 289623 21402 -10701 539474 -269737 -681332 340666 -746052 373026 -993382 496691 -333880 166940 -632724 316362 909690 -454845 86680 -43340 236688 -118344 -29102 14551 6252 -3126 -440612 220306 -878460 439230 649538 -324769 -651632 325816 882...

output:

---------+-+-----------+-+-+---+-----+---+-+-+---+-+-+-+-+---+-----+-----+---+-+-----+-----+-+-+---+---+-+-----+-------+-+---+-----+-+-+-------+-+-+-+-+-------+-----+-+-+-------+-------+-+-+-------+---+-+---+-+---+-+-+-+---+-+-+-+-+---------+-----+-----+-+-+-+-+-+-+-+---+-+-+-------+---+-+-+-+-+-+--...

result:

ok single line: '---------+-+-----------+-+-+--...+---+-+-+-+-+-----+-+---------+'

Test #7:

score: -100
Time Limit Exceeded

input:

100000
-1 126247070 -63123535 -440273040 220136520 809537358 -404768679 -927404550 463702275 896759686 -448379843 155450002 -77725001 995415070 -497707535 -730811632 365405816 -223816910 111908455 255855870 -127927935 -78358522 39179261 190117110 -95058555 -61118274 30559137 243732804 -121866402 -48...

output:

-+---+---+-+-+-----+---+---+-------+-+-+---+-----+---+-+-+-----+-+-----+-----+-+---+-+---+---+-+-+-+-+-----------+---+-+-+-------+-+-+---+-----+-------+-+---+-+---------------+-----------------+-+-----+-+-+---+-+-+-+---+-+-----+-+-+---+-+-----+-+-+-----+-----+-+-+-----+-+-+-----+-+---+-+---+-+-+-+--...

result: