CSES - HIIT Open 2018 - Results
Submission details
Task:Letter Game
Sender:Ukkonen Fan Club
Submission time:2018-05-26 15:56:07
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.02 sdetails
#20.02 sdetails
#30.01 sdetails
#40.01 sdetails
#50.01 sdetails
#60.01 sdetails
#70.01 sdetails
#80.01 sdetails
#90.01 sdetails
#100.01 sdetails
#110.01 sdetails
#120.01 sdetails
#130.01 sdetails
#140.02 sdetails
#150.01 sdetails
#160.01 sdetails
#170.01 sdetails
#180.02 sdetails
#190.01 sdetails

Code

#include <bits/stdc++.h>
#define x real()
#define Y imag()
#define F first
#define S second
const double SIDE_THRESHOLD = 5;

int D2=300;
double MA=15.0   /180.0*3.14159265358979;


using namespace std;
char t[111][111];
typedef long long ll;
typedef complex<double> co;


long long d2(pair<int, int> a, pair<int, int> b){
    return (a.F-b.F)*(a.F-b.F)+(a.S-b.S)*(a.S-b.S);
}

pair<int, int> md(pair<int, int> a, pair<int, int> b){
    return {(a.F+b.F)/2, (a.S+b.S)/2};
}

double dotP(pair<int, int> a, pair<int, int> b){
    return a.F*b.F+a.S*b.S;
}


double angle(pair<int, int> a, pair<int, int> b){
    return acos(dotP(a,b)/sqrt(dotP(a,a)*dotP(b,b)));
}

bool ok(pair<int, int> a, pair<int, int> b, pair<int, int> c){
    pair<int, int> v1={b.F-a.F, b.S-a.S};
    pair<int, int> v2={c.F-b.F, c.S-b.S};
    return abs(angle(v1, v2))>MA;
}

void solve(){
    int n=100;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            cin>>t[i][j];
        }
    }
    vector<pair<int, int> > dh;
    vector<pair<int, int> > uh;
    for (int i=0;i<n;++i){
        bool f=0;
        int l=0;
        for (int j=0;j<n;++j){
            if (t[i][j]=='1'){
                if (!f) uh.push_back({i,j});
                f=1;
                l=j;
            }
        }
        if (f){
            dh.push_back({i,l});
        }
    }
    vector<pair<int, int> > dsh;
    vector<pair<int, int> > ush;
    dsh.push_back(dh[0]);
    ush.push_back(uh[0]);
    for (auto v:dh){
        if (dsh.size()==1){
            if (d2(v, dsh.back())<D2/2) continue;
            dsh.push_back(v);
        }else{
            if (!ok(dsh[dsh.size()-2], dsh[dsh.size()-1], v)) dsh.pop_back();
            if (d2(v, dsh.back())<D2) continue;
            dsh.push_back(v);
        }
    }
    for (auto v:uh){
        if (ush.size()==1) ush.push_back(v);
        else{
            if (!ok(ush[ush.size()-2], ush[ush.size()-1], v)) ush.pop_back();
            if (d2(v, ush.back())<D2) continue;
            ush.push_back(v);
        }
    }
    int minus=0;
    if (dsh[0]!=ush[0]){
        if (!ok(dsh[0], ush[0], ush[1]) || !ok(ush[0], dsh[0], dsh[1]) || d2(ush[0], dsh[0])<D2/2) ++minus;
    }
    if (dsh.back()!=ush.back()){
        if (!ok(dsh.back(), ush.back(), ush[ush.size()-2]) || !ok(ush.back(), dsh.back(), dsh[dsh.size()-2])  || d2(ush.back(), dsh.back())<D2/2) ++minus;
    }
    set<pair<int, int> > k;
    for (auto v:dsh) k.insert(v);
    for (auto v:ush) k.insert(v);
//     for (auto n:k) cout << n.F << ", " << n.S << endl;
    cout << k.size()-minus << "\n";
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t;
    cin >> t;
    for (int i=0;i<t;++i)solve();
  
}

Test details

Test 1

Verdict:

input
1
..

correct output
0

user output
(empty)

Test 2

Verdict:

input
2
A..B

correct output
0

user output
(empty)

Test 3

Verdict:

input
2
B..A

correct output
-1

user output
(empty)

Test 4

Verdict:

input
3
AA..BB

correct output
0

user output
(empty)

Test 5

Verdict:

input
3
AB..AB

correct output
-1

user output
(empty)

Test 6

Verdict:

input
3
AB..BA

correct output
2
ABBA..
A..ABB

user output
(empty)

Test 7

Verdict:

input
3
BA..AB

correct output
2
..BAAB
AAB..B

user output
(empty)

Test 8

Verdict:

input
3
BA..BA

correct output
-1

user output
(empty)

Test 9

Verdict:

input
3
BB..AA

correct output
2
..BBAA
AABB..

user output
(empty)

Test 10

Verdict:

input
100
BBABAABBBAAAAABBBBBBAAAABAAABA...

correct output
140
..ABAABBBAAAAABBBBBBAAAABAAABA...

user output
(empty)

Test 11

Verdict:

input
100
AABBABBAAABABBBBBBBBAABABAAAAB...

correct output
142
AA..ABBAAABABBBBBBBBAABABAAAAB...

user output
(empty)

Test 12

Verdict:

input
100
AAAAABAABBBABAABAAABABBAAAABAA...

correct output
134
AAAAA..ABBBABAABAAABABBAAAABAA...

user output
(empty)

Test 13

Verdict:

input
100
BBBAAAABAABABAABAABBBABBABABAA...

correct output
142
..BAAAABAABABAABAABBBABBABABAA...

user output
(empty)

Test 14

Verdict:

input
100
BABBBAAAAABABAAABBBAABBABABBBB...

correct output
138
..BBBAAAAABABAAABBBAABBABABBBB...

user output
(empty)

Test 15

Verdict:

input
100
ABAAAAABBAAAAAAAAAABABAABBBBBB...

correct output
126
A..AAAABBAAAAAAAAAABABAABBBBBB...

user output
(empty)

Test 16

Verdict:

input
100
ABBBBBABBABABABBBABAABAAAABBAA...

correct output
128
A..BBBABBABABABBBABAABAAAABBAA...

user output
(empty)

Test 17

Verdict:

input
100
BAAABBABBAAAABABAAABABABBAAABA...

correct output
139
..AABBABBAAAABABAAABABABBAAABA...

user output
(empty)

Test 18

Verdict:

input
100
BBBBBABBAAABBAABBBBBABABABAABA...

correct output
133
..BBBABBAAABBAABBBBBABABABAABA...

user output
(empty)

Test 19

Verdict:

input
100
BABBBBBBABBBABBBBBBAABABAAABAA...

correct output
128
..BBBBBBABBBABBBBBBAABABAAABAA...

user output
(empty)