oj.uz

Submission #544459

# Submission time Handle Problem Language Result Execution time Memory
544459 2022-04-02T01:11:10 Z ac2hu Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 1888 ms 262144 KB 
#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
void setIO(string name) {
	#ifdef DEBUG
	#else 
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
	#endif
}
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n;cin >> n;
    vector<pair<int,int>> a(n);
    for(auto &e : a){
        cin >> e.first >> e.second;
    }
    auto fit = [&](pair<int,int> a,pair<int,int> b) -> bool{
        // if b can't fit a 
        return (abs(b.first  - a.first) <= abs(b.second - a.second));
    };
    auto better = [&](pair<int,int> a, pair<int,int> b) -> bool{
        if(a.first + a.second > b.first + b.second)
            return true;
        return false;
    };
    vector<pair<int,int>> st;
    st.push_back(a[0]);
    for(int i = 1;i<n;i++){
        while(st.size() > 0 && fit(a[i], st.back()) && better(a[i], st.back())){
            st.pop_back();
        }
        if(st.size() == 0 || !fit(a[i], st.back())){//(!fit(a[i], st.back()) && !better(st.back(), a[i]))){
            st.push_back(a[i]);
        }
        deb(st);
    }
    // cout << fit(a[n - 1], st.back()) << " " << better(st.back(), a[n - 1]) << "\n";
    cout << st.size() << "\n";
}

Compilation message

lightningrod.cpp: In function 'void setIO(std::string)':
lightningrod.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lightningrod.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1638 ms 262144 KB Output is correct
2 Correct 1536 ms 262144 KB Output is correct
3 Correct 1493 ms 262144 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 1 ms 320 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 37 ms 5340 KB Output is correct
15 Correct 44 ms 5156 KB Output is correct
16 Correct 38 ms 5576 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1572 ms 240516 KB Output is correct
2 Correct 1538 ms 240208 KB Output is correct
3 Correct 1442 ms 235860 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1638 ms 262144 KB Output is correct
2 Correct 1536 ms 262144 KB Output is correct
3 Correct 1493 ms 262144 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 37 ms 5340 KB Output is correct
18 Correct 44 ms 5156 KB Output is correct
19 Correct 38 ms 5576 KB Output is correct
20 Correct 1572 ms 240516 KB Output is correct
21 Correct 1538 ms 240208 KB Output is correct
22 Correct 1442 ms 235860 KB Output is correct
23 Correct 1888 ms 223792 KB Output is correct
24 Correct 1768 ms 227980 KB Output is correct
25 Correct 1788 ms 213216 KB Output is correct