oj.uz

Submission #1099319

# Submission time Handle Problem Language Result Execution time Memory
1099319 2024-10-11T07:23:57 Z theSkeleton Tracks in the Snow (BOI13_tracks) C++17
34.5833 / 100
 2000 ms 955332 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 2084 ms 916084 KB Time limit exceeded
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1473 ms 78560 KB Output is correct
4 Execution timed out 2078 ms 731016 KB Time limit exceeded
5 Execution timed out 2069 ms 433192 KB Time limit exceeded
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1424 ms 78652 KB Output is correct
8 Execution timed out 2049 ms 766632 KB Time limit exceeded
9 Correct 5 ms 4700 KB Output is correct
10 Execution timed out 2136 ms 851260 KB Time limit exceeded
11 Execution timed out 2043 ms 704312 KB Time limit exceeded
12 Execution timed out 2107 ms 953908 KB Time limit exceeded
13 Execution timed out 2068 ms 426192 KB Time limit exceeded
14 Execution timed out 2050 ms 426028 KB Time limit exceeded
15 Execution timed out 2066 ms 918468 KB Time limit exceeded
16 Execution timed out 2069 ms 955332 KB Time limit exceeded
17 Execution timed out 2098 ms 802336 KB Time limit exceeded
18 Execution timed out 2095 ms 739000 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 30296 KB Output is correct
2 Execution timed out 2095 ms 741404 KB Time limit exceeded
3 Execution timed out 2084 ms 382276 KB Time limit exceeded
4 Execution timed out 2049 ms 299688 KB Time limit exceeded
5 Correct 141 ms 32596 KB Output is correct
6 Execution timed out 2093 ms 873016 KB Time limit exceeded
7 Correct 12 ms 31832 KB Output is correct
8 Correct 11 ms 30300 KB Output is correct
9 Execution timed out 2045 ms 226180 KB Time limit exceeded
10 Correct 1 ms 2396 KB Output is correct
11 Correct 12 ms 31232 KB Output is correct
12 Correct 1 ms 4700 KB Output is correct
13 Execution timed out 2117 ms 752128 KB Time limit exceeded
14 Execution timed out 2081 ms 435820 KB Time limit exceeded
15 Correct 16 ms 9564 KB Output is correct
16 Execution timed out 2080 ms 558580 KB Time limit exceeded
17 Execution timed out 2118 ms 421976 KB Time limit exceeded
18 Correct 63 ms 20560 KB Output is correct
19 Execution timed out 2085 ms 294568 KB Time limit exceeded
20 Execution timed out 2067 ms 241928 KB Time limit exceeded
21 Execution timed out 2071 ms 261868 KB Time limit exceeded
22 Correct 143 ms 32592 KB Output is correct
23 Execution timed out 2080 ms 410872 KB Time limit exceeded
24 Correct 132 ms 33364 KB Output is correct
25 Correct 369 ms 47184 KB Output is correct
26 Execution timed out 2068 ms 645408 KB Time limit exceeded
27 Execution timed out 2094 ms 691728 KB Time limit exceeded
28 Execution timed out 2089 ms 948288 KB Time limit exceeded
29 Execution timed out 2067 ms 684936 KB Time limit exceeded
30 Execution timed out 2073 ms 713468 KB Time limit exceeded
31 Execution timed out 2104 ms 852096 KB Time limit exceeded
32 Execution timed out 2059 ms 544300 KB Time limit exceeded