oj.uz

Submission #70138

# Submission time Handle Problem Language Result Execution time Memory
70138 2018-08-22T11:46:00 Z vanogam popa (BOI18_popa) C++14
100 / 100
 128 ms 700 KB 
#include<bits/stdc++.h>
#ifndef hax
#include<popa.h>
#endif // hax
using namespace std;
int a,s,mas[10002],d[10002],f[10002],d1[10002],f1[10002],g,h,j,k,l,i,n,m;
#ifdef hax
int query(int a,int b,int c,int d){
    int g1=mas[a],g2=mas[c];
    for(;a<=b;a++){
        g1=__gcd(mas[a],g1);
    }

    for(;c<=d;c++){
        g2=__gcd(mas[c],g2);
    }
//cout<<g1<<"  "<<g2<<endl;
    return g1==g2;
}
#endif
int solve(int n,int* d,int *f){
    for(int i=0;i<n;i++){
        d[i]=-1;
        f[i]=-1;
    }
    stack<int> q;
    q.push(0);
    int y;
    for(int i=1;i<n;i++){
        while(q.size()){//cout<<q.size();
            if(!query(q.top(),i,i,i)){
                //cout<<q.top()<<" "<<i<<endl;
                if(f[q.top()]!=-1)
                    d[i]=f[q.top()];
                    f[q.top()]=i;
                    break;
                }
                else{
                    y=q.top();//cout<<"("<<y<<")";cout<<i<<" "<<y<<" L"<<endl;
                    q.pop();
                }

        }

        if(!q.size()){d[i]=y;}
        q.push(i);
    }
    while(q.size()>1) q.pop();
    return q.top();

}
#ifdef hax
main(){
    cin>>n>>k;
    for(i=0;i<n;i++){
        cin>>mas[i];
    }
    l=solve(n,d,f);
    if(k!=l) {cout<<"!"<<l<<"!\n";} else
    cout<<"RROT IS OK : "<<l<<endl;
    for(i=0;i<n;i++){
        cin>>d1[i];
    }

    for(i=0;i<n;i++){
        cin>>f1[i];
    }

    for(i=0;i<n;i++){
        cout<<d[i];
        if(d[i]!=d1[i]) cout<<"!";
        cout<<" ";
    }
    cout<<endl;
    for(i=0;i<n;i++){
        cout<<f[i];
        if(f[i]!=f1[i]) cout<<"!";
        cout<<" ";
    }
    cout<<endl;

}
#endif
/*
6 3
12 4 16 2 2 20
-1 0 -1 1 -1 -1
-1 2 -1 4 5 -1
*/

Compilation message

popa.cpp: In function 'int solve(int, int*, int*)':
popa.cpp:33:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
                 if(f[q.top()]!=-1)
                 ^~
popa.cpp:35:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
                     f[q.top()]=i;
                     ^
popa.cpp:45:27: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(!q.size()){d[i]=y;}
                       ~~~~^~

Subtask #1
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 248 KB Output is correct
2 Correct 13 ms 308 KB Output is correct
3 Correct 14 ms 520 KB Output is correct
4 Correct 7 ms 520 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 520 KB Output is correct
2 Correct 63 ms 544 KB Output is correct
3 Correct 77 ms 544 KB Output is correct
4 Correct 77 ms 544 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 572 KB Output is correct
2 Correct 102 ms 572 KB Output is correct
3 Correct 128 ms 692 KB Output is correct
4 Correct 110 ms 700 KB Output is correct