oj.uz

Submission #198851

# Submission time Handle Problem Language Result Execution time Memory
198851 2020-01-27T21:00:46 Z brcode Drzava (COCI15_drzava) C++14
144 / 160
 1000 ms 53244 KB 
#include <iostream>
#include <iomanip>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4+5;
const long double eps = 0.000001;
bool visited[MAXN];
//long long test;
int n,k;
pair<pair<long long,long long>,long long> p[MAXN];
struct cmpf{
    inline bool operator()(const long long& i, const long long& j)const{
        if(p[i].first.second!=p[j].first.second){
             return p[i].first.second<p[j].first.second;
        }
         return i>j;
    }
};
set<int,cmpf> s1;
vector<int> v1[MAXN];
vector<int> tempv;
bool dp[MAXN][40];
bool dist(long long i,long long j,long double x){
    return (long double)((p[i].first.first-p[j].first.first)*(p[i].first.first-p[j].first.first))+((p[i].first.second-p[j].first.second)*(p[i].first.second-p[j].first.second))<=(long double)x*x;
}
void dfs(int curr){
    tempv.push_back(curr);
    visited[curr] = true;
    for(int x:v1[curr]){
        if(!visited[x]){
            dfs(x);
        }
    }
}
bool findsubset(){
    int m = tempv.size();
    m--;
    if(m>k){
        return true;
    }
    
    for(int i=0;i<=m+1;i++){
        for(int j=0;j<=k+1;j++){
            dp[i][j] = false;
        }
    }
    for(int mod = 0;mod<k;mod++){
        dp[m+1][mod] = !mod;
    }
    for(int i=m;i>=1;i--){
        for(int mod = 0;mod<k;mod++){
            
                dp[i][mod] = dp[i+1][mod];
            
            
            if(dp[i+1][(mod+p[tempv[i]].second)%k]){
                dp[i][mod] = true;
               
            }
        }
        if(dp[i+1][p[tempv[i]].second]){
            
            return true;
        }
    }
    return false;
    
    
}
bool check(long double x){
    for(int i=1;i<=n;i++){
        v1[i].clear();
        visited[i] = false;
    }
    s1.clear();
    int j = 1;
    for(int i=1;i<=n;i++){
   
        while((long double)(p[i].first.first-p[j].first.first)>x){
            
            
            s1.erase(j);
            j++;
        }
        
        
        if(!s1.empty()){
            int cnt = 0;
            p[n+1] = make_pair(make_pair(p[i].first.first,(long long)(p[i].first.second-(long long)x)),0);
            
            for(auto it = s1.lower_bound(n+1);it!=s1.end();it++){
                int idx = *it;
              
                if(p[idx].first.second>p[i].first.second+x){
                    break;
                }
                cnt++;
                if(cnt>=8*k){
                    return true;
                    
                }
                if(dist(i,idx,x)){
                    
                    v1[i].push_back(idx);
                    v1[idx].push_back(i);
                }
            }
        }
        s1.insert(i);
    }
    
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            tempv.clear();
            tempv.push_back(-1);
            dfs(i);
           
            if(findsubset()){
                return true;
            }
            
        }
    }
   
    return false;
}
int main() {
     ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&p[i].first.first,&p[i].first.second,&p[i].second);
        p[i].second%=k;
    }
    sort(p+1,p+n+1);
    long double l = 0;
    long double r = 1e8;
    long double ans = -1;
    while(r-l>eps){
        long double mid = (l+r)/2;
        
        if(check(mid)){
            
            ans = mid;
            r = mid-eps;
        }else{
            l = mid+eps;
        }
       
    }
   
  //  cout<<check(11163410)<<endl;
    if(ans == -1){
        printf("No solution!\n");
    }else{
        
        printf("%.3lf",(double)ans);
    }
}

Compilation message

drzava.cpp: In function 'int main()':
drzava.cpp:132:75: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d %d %d",&p[i].first.first,&p[i].first.second,&p[i].second);
                          ~~~~~~~~~~~~~~~~~                                ^
drzava.cpp:132:75: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
drzava.cpp:132:75: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
drzava.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~~
drzava.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&p[i].first.first,&p[i].first.second,&p[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1528 KB Output is correct
2 Correct 6 ms 1528 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 11 ms 1528 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1528 KB Output is correct
2 Correct 22 ms 2168 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 15 ms 1912 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1532 KB Output is correct
2 Correct 22 ms 2044 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1580 KB Output is correct
2 Correct 21 ms 2040 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 22 ms 2168 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 15 ms 1916 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 160 ms 5628 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1528 KB Output is correct
2 Execution timed out 1006 ms 50420 KB Time limit exceeded

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Execution timed out 1093 ms 48692 KB Time limit exceeded

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 847 ms 45180 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1528 KB Output is correct
2 Correct 993 ms 53244 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1528 KB Output is correct
2 Correct 885 ms 53244 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 548 ms 10736 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 566 ms 11000 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 591 ms 15712 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 644 ms 15584 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 524 ms 10208 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 561 ms 14716 KB Output is correct