Submission #971319

#	Time	Username	Problem	Language	Result	Execution time	Memory
971319		AIF_is_carving	IOI Fever (JOI21_fever)	C++17	11 / 100	1 ms	348 KiB

fever

#include <bits/stdc++.h>

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

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

int32_t 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 / 5
• Subtask 2: 0 / 8
• Subtask 3: 6 / 6
• Subtask 4: 0 / 6
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31