oj.uz

Submission #1099321

# Submission time Handle Problem Language Result Execution time Memory
1099321 2024-10-11T07:26:48 Z theSkeleton Tracks in the Snow (BOI13_tracks) C++17
34.5833 / 100
 2000 ms 986244 KB 
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e14
#define F first
#define S second
#define PB push_back
#define PF push_front
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define MT(a,b,c) make_tuple(a,b,c)
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const int mx = 4005;
int h,w;
bool seen[mx][mx];
char state[mx][mx];
deque<pair<int,int>> l[2];
pair<int,int> nei[]={MP(0,1),MP(0,-1),MP(1,0),MP(-1,0)};
bool c(int i,int j){
    return (i<0||h<=i||j<0||w<=j);
}
int main(){
    //std::ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    cin>>h>>w;
    for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
        cin>>state[i][j];
    int pc=0,cnt=0;
    char cc=state[h-1][w-1];
    l[pc].PB(MP(h-1,w-1));
    if(cc=='.'){
        cout<<0;
        return 0;
    }
    while(!l[pc].empty()){
        pair<int,int> r,d=l[pc].back();
        seen[d.F][d.S]=1;
        l[pc].pop_back();
        for(int i=0;i<4;i++){
            r=MP(d.F+nei[i].F,d.S+nei[i].S);
            if(!c(r.F,r.S))
            if (state[r.F][r.S]!='.'&&!seen[r.F][r.S]){
                if(state[r.F][r.S]==cc)
                    l[pc].push_front(MP(r.F,r.S));
                else
                    l[!pc].push_front(MP(r.F,r.S));
            }
        }
        if(l[pc].empty()){
            pc=!pc;cnt++;
            cc=((cc=='F')?'R':'F');
        }
    }
    cout<<cnt;
    return 0;
}

Compilation message

tracks.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization("O3")
      | 
tracks.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization("unroll-loops")
      |

Subtask #1
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2102 ms 986244 KB Time limit exceeded
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1409 ms 78480 KB Output is correct
4 Execution timed out 2063 ms 707720 KB Time limit exceeded
5 Execution timed out 2067 ms 421408 KB Time limit exceeded
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1593 ms 76784 KB Output is correct
8 Execution timed out 2059 ms 762884 KB Time limit exceeded
9 Correct 6 ms 4700 KB Output is correct
10 Execution timed out 2108 ms 831956 KB Time limit exceeded
11 Execution timed out 2109 ms 717424 KB Time limit exceeded
12 Execution timed out 2127 ms 917688 KB Time limit exceeded
13 Execution timed out 2053 ms 426856 KB Time limit exceeded
14 Execution timed out 2052 ms 431544 KB Time limit exceeded
15 Execution timed out 2070 ms 888828 KB Time limit exceeded
16 Execution timed out 2101 ms 974436 KB Time limit exceeded
17 Execution timed out 2098 ms 823996 KB Time limit exceeded
18 Execution timed out 2066 ms 730696 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 30300 KB Output is correct
2 Execution timed out 2121 ms 765124 KB Time limit exceeded
3 Execution timed out 2041 ms 298984 KB Time limit exceeded
4 Execution timed out 2061 ms 271540 KB Time limit exceeded
5 Correct 325 ms 23892 KB Output is correct
6 Execution timed out 2048 ms 704476 KB Time limit exceeded
7 Correct 12 ms 31580 KB Output is correct
8 Correct 12 ms 30300 KB Output is correct
9 Execution timed out 2096 ms 226076 KB Time limit exceeded
10 Correct 2 ms 2392 KB Output is correct
11 Correct 13 ms 31068 KB Output is correct
12 Correct 2 ms 4700 KB Output is correct
13 Execution timed out 2135 ms 741548 KB Time limit exceeded
14 Execution timed out 2089 ms 436168 KB Time limit exceeded
15 Correct 39 ms 8016 KB Output is correct
16 Execution timed out 2093 ms 542708 KB Time limit exceeded
17 Execution timed out 2023 ms 398696 KB Time limit exceeded
18 Correct 151 ms 15956 KB Output is correct
19 Execution timed out 2088 ms 290364 KB Time limit exceeded
20 Execution timed out 2048 ms 227020 KB Time limit exceeded
21 Execution timed out 2106 ms 251848 KB Time limit exceeded
22 Correct 314 ms 23892 KB Output is correct
23 Execution timed out 2044 ms 302584 KB Time limit exceeded
24 Correct 311 ms 24724 KB Output is correct
25 Correct 662 ms 31584 KB Output is correct
26 Execution timed out 2099 ms 583192 KB Time limit exceeded
27 Execution timed out 2098 ms 543092 KB Time limit exceeded
28 Execution timed out 2098 ms 736060 KB Time limit exceeded
29 Execution timed out 2060 ms 545912 KB Time limit exceeded
30 Execution timed out 2082 ms 599400 KB Time limit exceeded
31 Execution timed out 2095 ms 754844 KB Time limit exceeded
32 Execution timed out 2057 ms 437868 KB Time limit exceeded