oj.uz

Submission #1099304

# Submission time Handle Problem Language Result Execution time Memory
1099304 2024-10-11T06:59:48 Z theSkeleton Tracks in the Snow (BOI13_tracks) C++17
34.5833 / 100
 2000 ms 1048576 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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 = 4e3+5;
int h,w;
bool seen[mx][mx];
char state[mx][mx];
deque<pair<int,int>> l[2];
void c(int i,int j,char s,bool p){
    if(i<0||h<=i||j<0||w<=j)return;
    if (state[i][j]=='.')   return;
    if(seen[i][j])          return;
    if(state[i][j]==s)
        l[p].push_front(MP(i,j));
    else
        l[!p].push_front(MP(i,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));
    while(!l[pc].empty()){
        auto d=l[pc].back();
        seen[d.F][d.S]=1;
        l[pc].pop_back();
        c(d.F+1,d.S,cc,pc);
        c(d.F-1,d.S,cc,pc);
        c(d.F,d.S+1,cc,pc);
        c(d.F,d.S-1,cc,pc);
        if(l[pc].empty()){
            pc=!pc;cnt++;
            cc=((cc=='F')?'R':'F');
        }
    }
    cout<<cnt;
    return 0;
}

Subtask #1
8.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1950 ms 1048576 KB Execution killed with signal 9
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1503 ms 74560 KB Output is correct
4 Execution timed out 2070 ms 749976 KB Time limit exceeded
5 Execution timed out 2072 ms 459048 KB Time limit exceeded
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1485 ms 74760 KB Output is correct
8 Execution timed out 2079 ms 818616 KB Time limit exceeded
9 Correct 7 ms 3160 KB Output is correct
10 Execution timed out 2112 ms 1004940 KB Time limit exceeded
11 Execution timed out 2062 ms 810464 KB Time limit exceeded
12 Execution timed out 2081 ms 1048576 KB Time limit exceeded
13 Execution timed out 2087 ms 455212 KB Time limit exceeded
14 Execution timed out 2061 ms 465960 KB Time limit exceeded
15 Runtime error 1951 ms 1048576 KB Execution killed with signal 9
16 Runtime error 1908 ms 1048576 KB Execution killed with signal 9
17 Execution timed out 2041 ms 888116 KB Time limit exceeded
18 Execution timed out 2079 ms 790688 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 30296 KB Output is correct
2 Execution timed out 2109 ms 857140 KB Time limit exceeded
3 Execution timed out 2077 ms 364112 KB Time limit exceeded
4 Execution timed out 2051 ms 302248 KB Time limit exceeded
5 Correct 149 ms 32596 KB Output is correct
6 Execution timed out 2036 ms 1048576 KB Time limit exceeded
7 Correct 14 ms 31836 KB Output is correct
8 Correct 13 ms 30292 KB Output is correct
9 Execution timed out 2088 ms 223752 KB Time limit exceeded
10 Correct 1 ms 2396 KB Output is correct
11 Correct 12 ms 31244 KB Output is correct
12 Correct 1 ms 1628 KB Output is correct
13 Execution timed out 2125 ms 837436 KB Time limit exceeded
14 Execution timed out 2070 ms 442296 KB Time limit exceeded
15 Correct 21 ms 9040 KB Output is correct
16 Execution timed out 2061 ms 561252 KB Time limit exceeded
17 Execution timed out 2081 ms 420144 KB Time limit exceeded
18 Correct 65 ms 19796 KB Output is correct
19 Execution timed out 2045 ms 328516 KB Time limit exceeded
20 Execution timed out 2047 ms 240336 KB Time limit exceeded
21 Execution timed out 2053 ms 261204 KB Time limit exceeded
22 Correct 144 ms 32596 KB Output is correct
23 Execution timed out 2059 ms 409596 KB Time limit exceeded
24 Correct 151 ms 33620 KB Output is correct
25 Correct 336 ms 47440 KB Output is correct
26 Execution timed out 2043 ms 766824 KB Time limit exceeded
27 Execution timed out 2130 ms 780396 KB Time limit exceeded
28 Execution timed out 2086 ms 1048576 KB Time limit exceeded
29 Execution timed out 2065 ms 719808 KB Time limit exceeded
30 Execution timed out 2079 ms 775704 KB Time limit exceeded
31 Execution timed out 2057 ms 1015772 KB Time limit exceeded
32 Execution timed out 2070 ms 620100 KB Time limit exceeded