oj.uz

Submission #72323

# Submission time Handle Problem Language Result Execution time Memory
72323 2018-08-26T07:08:04 Z 신딩없는 신딩팀(#2212, willi19, andy627, maruii) Hill Reconstruction (FXCUP3_hill) C++17
32 / 100
 1500 ms 146140 KB 
#include <stdio.h>
#include <queue>
#include <set>
#include <algorithm>
#define LL long long
#define pll pair<LL,LL>
#define x first
#define y second
using namespace std;

pll cor[333333];

struct tani{
    int idx1,idx2;

    bool operator<(const tani A)const{
        return (cor[idx2].y-cor[idx1].y)*(cor[A.idx2].x-cor[A.idx1].x)<(cor[A.idx2].y-cor[A.idx1].y)*(cor[idx2].x-cor[idx1].x);
    }
};

priority_queue<tani> pq,del;
set<int> st;

LL gcd(LL x,LL y){
    return y?gcd(y,x%y):x;
}

LL tri(int i,int j,int k){
    return abs(cor[i].x*cor[j].y+cor[j].x*cor[k].y+cor[k].x*cor[i].y-cor[j].x*cor[i].y-cor[k].x*cor[j].y-cor[i].x*cor[k].y);
}

int main(){
    LL n,c;

    scanf("%lld %lld",&n,&c); c<<=1;
    for(int i=1;i<=n;i++) scanf("%lld",&cor[i].x);
    for(int i=1;i<=n;i++) scanf("%lld",&cor[i].y);

    for(int i=1;i<n;i++) pq.push({i,i+1});
    for(int i=1;i<=n;i++) st.insert(i);

    while(1){
        int idx1=pq.top().idx1;
        int idx2=pq.top().idx2;
        set<int>::iterator it=st.find(idx1);

//        printf("%d %d %lld\n",idx1,idx2,c);

        if(it==st.begin()){
            LL g=gcd(cor[idx2].y-cor[idx1].y,cor[idx2].x-cor[idx1].x);
            printf("%lld/%lld",(cor[idx2].y-cor[idx1].y)/g,(cor[idx2].x-cor[idx1].x)/g);
            return 0;
        }

        int idx0=*(--it);
        LL siz=tri(idx0,idx1,idx2);

//        printf("%d %d %d %lld %lld\n",idx0,idx1,idx2,c,siz);

        if(c>=siz) c-=siz;
        else{
            LL g=gcd(cor[idx2].y-cor[idx1].y,cor[idx2].x-cor[idx1].x);
            printf("%lld/%lld",(cor[idx2].y-cor[idx1].y)/g,(cor[idx2].x-cor[idx1].x)/g);
            return 0;
        }

        del.push({idx0,idx1}); del.push({idx1,idx2}); st.erase(idx1);
        while(!pq.empty() && !del.empty()){
            tani top1=pq.top(),top2=del.top();
            if(top1.idx1==top2.idx1 && top1.idx2==top2.idx2) pq.pop(),del.pop();
            else break;
        }
        pq.push({idx0,idx2});
    }

    return 0;
}

Compilation message

hill.cpp: In function 'int main()':
hill.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld",&n,&c); c<<=1;
     ~~~~~^~~~~~~~~~~~~~~~~~~
hill.cpp:36:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%lld",&cor[i].x);
                           ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:37:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%lld",&cor[i].y);
                           ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 4 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct

Subtask #2
0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 484 KB Output is correct
4 Correct 3 ms 484 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 4 ms 644 KB Output is correct
7 Correct 3 ms 644 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 228 ms 21572 KB Output is correct
10 Correct 200 ms 21572 KB Output is correct
11 Execution timed out 1562 ms 146140 KB Time limit exceeded
12 Halted 0 ms 0 KB -