#1954780

Solution for 2310: Rose Garden Witch by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 60    
01.14 sec    17828 KB    75 lines     1998 bytes    2016-08-08 14:55
#include<bits/stdc++.h>

using namespace std;

struct I{I(){ios::sync_with_stdio(false);cin.tie(0);}}init;

const double eps=1e-10;
int main(){
    int R,C,res=0;
    cin>>R>>C;
    vector<string> f(R);
    for(int i=0;i<R;i++){
        cin>>f[i];f[i]+="..";
    }
    reverse(f.begin(),f.end());
    f.push_back(string(C+2,'.'));
    f.push_back(string(C+2,'.'));
    using T=tuple<int,int>;
    map<double,T> d;
    for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++){
            auto dd=atan2(i,j);
            if(d.count(dd))d[dd]=min(d[dd],T(i,j));
            else d[dd]=T(i,j);
        }
    vector<int> X(R,C+1);
    vector<int> Y(C,1);
    for(auto &it:d){
        int cross=0;
        if(f[0][0]=='#')cross++;
        int l=0,m=0,r=0;
        int x,y;
        tie(x,y)=it.second;
        double k=y/(double)x;
        for(int i=0;i<R;i++){
            double yy=k*(i+1);
            while(yy+eps<X[i])X[i]--;
            if(yy-eps<X[i]&&X[i]<yy+eps){
                int mask=0;
                if(f[i][X[i]-1]=='#')mask|=1;
                if(f[i][X[i]]=='#')mask|=2;
                if(f[i+1][X[i]-1]=='#')mask|=4;
                if(f[i+1][X[i]]=='#')mask|=8;
                switch(mask){
                case 0:
                case 15:break;
                case 13:
                case 2:r+=2;break;
                case 11:
                case 4:l+=2;break;
                default:cross++;break;
                }

            }
            else{
                if(f[i][X[i]]!=f[i+1][X[i]])cross++;
            }
        }
        k=x/(double)y;
        for(int i=0;i<C;i++){
            double xx=k*(i+1);
            while(xx-eps>Y[i]&&Y[i]<=R)Y[i]++;
            if(xx-eps<Y[i]&&Y[i]<xx+eps)continue;
            if(f[Y[i]-1][i]!=f[Y[i]-1][i+1])cross++;
        }
        //cout<<x<<" "<<y<<endl;
        //if(x==3&&y==8)cout<<cross<<" "<<l<<" " <<r<<endl;
        res=max(res,1+(cross+max({l,r}))/2);
        //cout<<res<<endl;
    }
    cout<<res<<endl;
    return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 71/71 C++11 CPU: 01.14 sec Memory: 17828 KB Length: 1998 B 2016-08-08 14:55 2016-08-08 14:56
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.00 sec 3332 KB
Case #2: : Accepted 00.00 sec 3448 KB
Case #3: : Accepted 00.00 sec 3428 KB
Case #4: : Accepted 00.00 sec 3392 KB
Case #5: : Accepted 00.00 sec 3472 KB
Case #6: : Accepted 00.00 sec 3376 KB
Case #7: : Accepted 00.00 sec 3276 KB
Case #8: : Accepted 00.00 sec 3360 KB
Case #9: : Accepted 00.00 sec 3288 KB
Case #10: : Accepted 00.00 sec 3276 KB
Case #11: : Accepted 00.00 sec 3392 KB
Case #12: : Accepted 00.00 sec 3292 KB
Case #13: : Accepted 00.00 sec 3268 KB
Case #14: : Accepted 00.00 sec 3500 KB
Case #15: : Accepted 00.00 sec 3300 KB
Case #16: : Accepted 00.00 sec 3460 KB
Case #17: : Accepted 00.00 sec 3480 KB
Case #18: : Accepted 00.00 sec 3304 KB
Case #19: : Accepted 00.00 sec 3492 KB
Case #20: : Accepted 00.00 sec 3508 KB
Case #21: : Accepted 00.00 sec 3428 KB
Case #22: : Accepted 00.00 sec 3452 KB
Case #23: : Accepted 00.00 sec 3488 KB
Case #24: : Accepted 00.00 sec 3456 KB
Case #25: : Accepted 00.00 sec 3392 KB
Case #26: : Accepted 00.00 sec 3468 KB
Case #27: : Accepted 00.00 sec 3544 KB
Case #28: : Accepted 00.00 sec 3568 KB
Case #29: : Accepted 00.00 sec 3580 KB
Case #30: : Accepted 00.00 sec 3488 KB
Case #31: : Accepted 00.00 sec 3468 KB
Case #32: : Accepted 00.00 sec 3488 KB
Case #33: : Accepted 00.00 sec 3556 KB
Case #34: : Accepted 00.00 sec 3480 KB
Case #35: : Accepted 00.00 sec 3220 KB
Case #36: : Accepted 00.00 sec 3464 KB
Case #37: : Accepted 00.00 sec 3644 KB
Case #38: : Accepted 00.00 sec 3356 KB
Case #39: : Accepted 00.69 sec 13664 KB
Case #40: : Accepted 01.07 sec 17688 KB
Case #41: : Accepted 01.10 sec 17520 KB
Case #42: : Accepted 01.08 sec 17644 KB
Case #43: : Accepted 01.07 sec 17648 KB
Case #44: : Accepted 01.06 sec 17624 KB
Case #45: : Accepted 00.00 sec 3412 KB
Case #46: : Accepted 00.00 sec 3432 KB
Case #47: : Accepted 00.00 sec 3432 KB
Case #48: : Accepted 00.00 sec 3468 KB
Case #49: : Accepted 00.00 sec 3412 KB
Case #50: : Accepted 00.00 sec 3424 KB
Case #51: : Accepted 00.00 sec 3436 KB
Case #52: : Accepted 01.06 sec 17828 KB
Case #53: : Accepted 01.07 sec 17620 KB
Case #54: : Accepted 01.07 sec 17676 KB
Case #55: : Accepted 01.14 sec 17624 KB
Case #56: : Accepted 01.10 sec 17824 KB
Case #57: : Accepted 00.00 sec 3384 KB
Case #58: : Accepted 00.00 sec 3428 KB
Case #59: : Accepted 00.00 sec 3396 KB
Case #60: : Accepted 00.00 sec 3284 KB
Case #61: : Accepted 00.05 sec 5084 KB
Case #62: : Accepted 00.05 sec 5152 KB
Case #63: : Accepted 00.05 sec 5124 KB
Case #64: : Accepted 01.10 sec 17620 KB
Case #65: : Accepted 00.00 sec 3472 KB
Case #66: : Accepted 00.00 sec 3412 KB
Case #67: : Accepted 00.00 sec 3436 KB
Case #68: : Accepted 00.00 sec 3384 KB
Case #69: : Accepted 00.00 sec 3392 KB
Case #70: : Accepted 00.00 sec 3464 KB
Case #71: : Accepted 00.00 sec 3392 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags