oj.uz

Submission #971313

# Submission time Handle Problem Language Result Execution time Memory
971313 2024-04-28T11:09:46 Z AIF_is_carving IOI Fever (JOI21_fever) C++17
11 / 100
 1 ms 456 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, int>> v;

vector<pair<int, int>> direction={{1, 0},{-1,0}, {0, 1}, {0, -1}};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n; cin>>n;
    
    for(int i=0; i<n; i++){
        int x, y; cin>>x>>y;
        v.push_back({x, y});
    }

    for(int i=1; i<n; i++){
        v[i].first-=v[0].first;
        v[i].second-=v[0].second;
    }

    v[0]={0,0};

    
    pair<int, int> dir[n];
    
    for(int i = 0; i < n; i++) {
        dir[i] = {0, 0};
    }
    
    set<int> fixed, not_fixed;
    
    int mx = 0;
    

    for(auto d: direction) {
      
        fixed.clear(), not_fixed.clear();
        
        dir[0] = d;
        int time[n];
        time[0] = 0;
        fixed.insert(0);
        
        for(int i = 1; i < n; i++) {
            not_fixed.insert(i);
            time[i] = -1;
        }
      
        
        int cnt;
        while(true) {
            
            set<int> non_fixed_to_fixed;
            
            cnt = 0;
            /// count this here
            for(int nf: not_fixed) {
                for(int f: fixed) {
                    if(dir[f] == direction[0]) {
                        if((v[f].first - v[nf].first) == -(v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {0, 1};
                        }
                        if((v[f].first - v[nf].first) == (v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {0, -1};
                        }
                    } else if(dir[f] == direction[3]) {
                        if((v[f].first - v[nf].first) == -(v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {-1, 0};
                        }
                        if((v[f].first - v[nf].first) == (v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {1, 0};
                        }
                    } else if(dir[f] == direction[2]) {
                        if((v[f].first - v[nf].first) == -(v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {1, 0};
                        }
                        if((v[f].first - v[nf].first) == (v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {-1, 0};
                        }
                    } else if(dir[f] == direction[1]) {
                        if((v[f].first - v[nf].first) == -(v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {0, -1};
                        }
                        if((v[f].first - v[nf].first) == (v[f].second - v[nf].second)) {
                            if(time[f] > abs((v[f].first - v[nf].first))) continue;
                            time[nf] = abs((v[f].first - v[nf].first));
                            non_fixed_to_fixed.insert(nf);
                            cnt++;
                            dir[nf] = {0, 1};
                        }
                    }
                }
            }
            
            for(int nftf: non_fixed_to_fixed) {
                not_fixed.erase(not_fixed.find(nftf));
                fixed.insert(nftf);
            }
          
            
            if(not_fixed.size() == 0) break;
          
            if(cnt == 0) break;
        }
      
        mx = max(mx, int(fixed.size()));
        
        
    }
  
    cout << (mx) << endl;
    
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 456 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 456 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Incorrect 0 ms 348 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 456 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Incorrect 0 ms 348 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 456 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Incorrect 0 ms 348 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 456 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Incorrect 0 ms 348 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #7
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 456 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 1 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Incorrect 0 ms 348 KB Output isn't correct
34 Halted 0 ms 0 KB -