QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#847907#8236. Snake MoveRed0WA 458ms167584kbC++205.3kb2025-01-08 13:03:462025-01-08 13:03:47

Judging History

你现在查看的是最新测评结果

  • [2025-01-08 13:03:47]
  • 评测
  • 测评结果:WA
  • 用时:458ms
  • 内存:167584kb
  • [2025-01-08 13:03:46]
  • 提交

answer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

//Debug Template:
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

//#define int long long

//Random Number Generator:
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x^(x>>30))*0xbf58476d1ce4e5b9;
        x = (x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = rng();
        return splitmix64(x+FIXED_RANDOM);
    }
};

//Custom Data Structures:
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using safe_set = unordered_set<T, custom_hash>;
template<typename T, typename V> using safe_map = unordered_map<T, V, custom_hash>;
template<typename T> using vc = vector<T>; template<typename T> using vvc = vc<vc<T>>; template<typename T> using vvvc = vc<vvc<T>>;
template<typename T, int V> using ar = array<T, V>;
template<typename T, typename V> using pr = pair<T, V>;
using vi = vc<int>; using vvi = vvc<int>; using vvvi = vvvc<int>;
using pii = pr<int, int>;

//Macros:
#define repl(i, a, b) for(int i = a; i < b; ++i)
#define repe(i, a, b) for(int i = a; i <= b; ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pow(b, p) (int)pow(b, p)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fir first
#define sec second
#define lsb(x) (int)__builtin_ctzll(x)
#define msb(x) (int)(63-__builtin_clzll(x))
#define yes cout << "YES\n"
#define no cout << "NO\n"

#define readall(x) trav(it, x) cin >> it;
#define printall(x) trav(it, x) cout << it << " ";
#define getmin(x) *min_element(all(x))
#define getmax(x) *max_element(all(x))

//c Problem Info:
const int MAX_N = 200005;
const int MAX_M = 200005;
const int INF = 1000000000;
const int MOD = pow(2, 64);

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    //represents if some square is a snake and also represents distance+1 from head;
    vvi org_snake(n+1, vi(m+1, 0));
    int hx = 0, hy = 0;
    repe(i, 1, k) {
        int x, y;
        cin >> x >> y;

        if (i == 1) hx = x, hy = y;
        org_snake[x][y] = i;
    }

    vvc<char> grid(n+1, vc<char>(m+1));
    repe(i, 1, n) {
        repe(j, 1, m) cin >> grid[i][j];
    }

    vvi dist(n+1, vi(m+1, INF));
    int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
    int mtime = n+m+k;
    vvc<pii> process(mtime+1);
    process[0].pb({hx, hy});
    dist[hx][hy] = 0;
    repe(t, 0, mtime) {
        for (auto &[cx, cy] : process[t]) {
            if (dist[cx][cy] < t) continue;
            //transition to next locations, up, down, left, right;
            repl(i, 0, 4) {
                int nx = cx+dx[i], ny = cy+dy[i];
                if (nx < 1 || nx > n || ny < 1 || ny > m || dist[nx][ny] != INF || grid[nx][ny] == '#') continue;
                if (org_snake[nx][ny] != 0) {
                    //check to see if the head will hit the body;
                    int steps_needed = k-org_snake[nx][ny]-t;
                    if (steps_needed > 0) {
                        dist[nx][ny] = t+1+steps_needed;
                        process[t+1+steps_needed].pb({nx, ny});
                    } else {
                        dist[nx][ny] = t+1;
                        process[t+1].pb({nx, ny});
                    }
                } else {
                    dist[nx][ny] = t+1;
                    process[t+1].pb({nx, ny});
                }
            }
        }
    }

    __int128_t ans = 0, mod = 2;
    repe(i, 1, 63) mod *= 2;
    repe(i, 1, n) {
        repe(j, 1, m) {
            if (dist[i][j] != INF) {
                ans = (ans+__int128_t(dist[i][j])*__int128_t(dist[i][j])%mod)%mod;
            }
        }
    }

    //debug(dist);
    cout << uint64_t(ans) << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    //cin >> t;

    while(t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3776kb

input:

4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....

output:

293

result:

ok single line: '293'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

2 2 4
1 1
1 2
2 2
2 1
..
..

output:

14

result:

ok single line: '14'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 335ms
memory: 162104kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 436ms
memory: 135852kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 76ms
memory: 82932kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 73ms
memory: 80280kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 346ms
memory: 160888kb

input:

2900 3000 10
2883 1758
2883 1759
2883 1760
2883 1761
2883 1762
2884 1762
2884 1763
2883 1763
2882 1763
2882 1764
........................................................#............................#........................................................................................................

output:

49803365625286

result:

ok single line: '49803365625286'

Test #9:

score: 0
Accepted
time: 448ms
memory: 141972kb

input:

3000 3000 10
2015 1932
2015 1931
2015 1930
2015 1929
2016 1929
2017 1929
2018 1929
2018 1928
2018 1927
2017 1927
#...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......

output:

22509095749285

result:

ok single line: '22509095749285'

Test #10:

score: 0
Accepted
time: 64ms
memory: 80200kb

input:

3000 2900 10
326 1781
325 1781
325 1782
325 1783
325 1784
324 1784
324 1783
323 1783
323 1782
324 1782
##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...

output:

40571

result:

ok single line: '40571'

Test #11:

score: 0
Accepted
time: 64ms
memory: 80228kb

input:

2900 3000 10
2447 135
2447 136
2447 137
2447 138
2447 139
2447 140
2448 140
2448 139
2449 139
2449 138
.#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...

output:

2705

result:

ok single line: '2705'

Test #12:

score: 0
Accepted
time: 359ms
memory: 167584kb

input:

3000 3000 100
2573 1917
2572 1917
2572 1916
2573 1916
2574 1916
2574 1915
2573 1915
2572 1915
2571 1915
2571 1914
2570 1914
2570 1915
2569 1915
2569 1916
2568 1916
2568 1917
2569 1917
2570 1917
2570 1916
2571 1916
2571 1917
2571 1918
2570 1918
2569 1918
2569 1919
2570 1919
2571 1919
2571 1920
2572 1...

output:

41693682087973

result:

ok single line: '41693682087973'

Test #13:

score: 0
Accepted
time: 425ms
memory: 137424kb

input:

3000 2900 56
923 228
922 228
921 228
920 228
919 228
919 227
919 226
920 226
920 227
921 227
922 227
922 226
922 225
921 225
921 224
921 223
920 223
920 222
920 221
921 221
921 222
922 222
923 222
924 222
925 222
925 223
924 223
923 223
922 223
922 224
923 224
923 225
924 225
924 224
925 224
925 225...

output:

36262204093655

result:

ok single line: '36262204093655'

Test #14:

score: 0
Accepted
time: 72ms
memory: 80208kb

input:

2900 3000 100
2357 817
2357 818
2357 819
2358 819
2359 819
2360 819
2360 820
2361 820
2361 819
2361 818
2360 818
2360 817
2361 817
2362 817
2362 818
2363 818
2364 818
2365 818
2365 817
2364 817
2363 817
2363 816
2363 815
2362 815
2362 814
2361 814
2361 815
2360 815
2360 816
2359 816
2358 816
2358 81...

output:

4878972

result:

ok single line: '4878972'

Test #15:

score: 0
Accepted
time: 63ms
memory: 82908kb

input:

3000 3000 97
2987 2472
2986 2472
2986 2471
2985 2471
2985 2470
2985 2469
2984 2469
2983 2469
2983 2468
2982 2468
2981 2468
2980 2468
2979 2468
2978 2468
2977 2468
2977 2469
2978 2469
2978 2470
2977 2470
2976 2470
2976 2471
2977 2471
2977 2472
2978 2472
2978 2473
2977 2473
2976 2473
2976 2472
2975 24...

output:

1992372

result:

ok single line: '1992372'

Test #16:

score: 0
Accepted
time: 311ms
memory: 161560kb

input:

3000 2900 22
2673 1308
2673 1309
2673 1310
2672 1310
2672 1309
2672 1308
2672 1307
2671 1307
2671 1306
2671 1305
2672 1305
2672 1306
2673 1306
2674 1306
2674 1305
2675 1305
2675 1306
2675 1307
2675 1308
2674 1308
2674 1307
2673 1307
......................................................................

output:

39910190747333

result:

ok single line: '39910190747333'

Test #17:

score: 0
Accepted
time: 430ms
memory: 135888kb

input:

2900 3000 72
820 2426
820 2427
820 2428
820 2429
820 2430
821 2430
821 2429
821 2428
822 2428
822 2429
822 2430
823 2430
824 2430
824 2429
824 2428
825 2428
825 2427
824 2427
824 2426
824 2425
825 2425
825 2426
826 2426
827 2426
828 2426
828 2427
829 2427
829 2426
830 2426
830 2427
830 2428
830 2429...

output:

30022933538350

result:

ok single line: '30022933538350'

Test #18:

score: 0
Accepted
time: 65ms
memory: 82876kb

input:

3000 3000 77
2008 1630
2007 1630
2007 1629
2007 1628
2006 1628
2005 1628
2004 1628
2004 1629
2003 1629
2002 1629
2001 1629
2001 1628
2000 1628
2000 1627
2000 1626
1999 1626
1999 1627
1999 1628
1999 1629
1999 1630
1999 1631
1999 1632
2000 1632
2000 1633
2000 1634
2001 1634
2001 1635
2001 1636
2002 16...

output:

385875

result:

ok single line: '385875'

Test #19:

score: 0
Accepted
time: 67ms
memory: 80372kb

input:

3000 2900 31
1343 2185
1342 2185
1342 2184
1341 2184
1341 2185
1341 2186
1341 2187
1340 2187
1340 2188
1339 2188
1338 2188
1337 2188
1336 2188
1336 2187
1337 2187
1337 2186
1337 2185
1337 2184
1338 2184
1338 2183
1337 2183
1336 2183
1335 2183
1335 2184
1334 2184
1334 2185
1334 2186
1335 2186
1335 21...

output:

97830

result:

ok single line: '97830'

Test #20:

score: 0
Accepted
time: 347ms
memory: 161728kb

input:

2900 3000 113
551 1058
551 1057
552 1057
552 1056
553 1056
553 1055
552 1055
551 1055
551 1054
552 1054
552 1053
552 1052
552 1051
551 1051
551 1052
551 1053
550 1053
550 1052
549 1052
549 1051
548 1051
548 1050
547 1050
547 1051
546 1051
545 1051
545 1050
545 1049
545 1048
544 1048
544 1049
544 105...

output:

35257969420026

result:

ok single line: '35257969420026'

Test #21:

score: 0
Accepted
time: 412ms
memory: 159324kb

input:

3000 3000 43
734 2607
733 2607
733 2608
733 2609
732 2609
732 2610
733 2610
734 2610
734 2609
734 2608
735 2608
735 2607
735 2606
735 2605
736 2605
736 2604
735 2604
734 2604
734 2603
735 2603
735 2602
735 2601
734 2601
734 2602
733 2602
733 2603
732 2603
731 2603
730 2603
730 2604
730 2605
730 2606...

output:

44813406952069

result:

ok single line: '44813406952069'

Test #22:

score: 0
Accepted
time: 419ms
memory: 145460kb

input:

3000 2900 31
2017 1649
2016 1649
2016 1648
2016 1647
2017 1647
2017 1646
2017 1645
2016 1645
2015 1645
2014 1645
2014 1644
2015 1644
2015 1643
2014 1643
2013 1643
2013 1644
2013 1645
2013 1646
2014 1646
2014 1647
2014 1648
2013 1648
2013 1649
2014 1649
2014 1650
2015 1650
2015 1649
2015 1648
2015 16...

output:

21058834151672

result:

ok single line: '21058834151672'

Test #23:

score: 0
Accepted
time: 446ms
memory: 135420kb

input:

2900 3000 28
1314 1304
1313 1304
1312 1304
1312 1305
1311 1305
1311 1304
1311 1303
1310 1303
1310 1304
1310 1305
1310 1306
1311 1306
1311 1307
1312 1307
1312 1308
1312 1309
1313 1309
1313 1310
1312 1310
1311 1310
1311 1309
1311 1308
1310 1308
1309 1308
1309 1309
1309 1310
1310 1310
1310 1309
..##..#...

output:

17072462334840

result:

ok single line: '17072462334840'

Test #24:

score: 0
Accepted
time: 74ms
memory: 83164kb

input:

3000 3000 150
1859 868
1860 868
1860 867
1859 867
1859 866
1859 865
1858 865
1858 866
1857 866
1857 865
1856 865
1856 864
1856 863
1856 862
1856 861
1856 860
1856 859
1857 859
1857 858
1858 858
1859 858
1859 859
1858 859
1858 860
1859 860
1860 860
1860 861
1859 861
1858 861
1858 862
1858 863
1857 86...

output:

450198912

result:

ok single line: '450198912'

Test #25:

score: 0
Accepted
time: 71ms
memory: 80184kb

input:

3000 2900 70
358 1006
359 1006
359 1005
358 1005
357 1005
357 1004
358 1004
358 1003
358 1002
359 1002
359 1003
359 1004
360 1004
361 1004
361 1003
360 1003
360 1002
360 1001
360 1000
359 1000
359 999
358 999
358 1000
357 1000
357 999
356 999
355 999
355 1000
356 1000
356 1001
356 1002
356 1003
355 ...

output:

379808

result:

ok single line: '379808'

Test #26:

score: 0
Accepted
time: 72ms
memory: 80440kb

input:

2900 3000 29
1355 1861
1356 1861
1356 1862
1355 1862
1355 1863
1354 1863
1354 1862
1353 1862
1352 1862
1352 1863
1351 1863
1351 1864
1351 1865
1351 1866
1352 1866
1352 1867
1351 1867
1351 1868
1352 1868
1352 1869
1353 1869
1353 1868
1353 1867
1354 1867
1354 1866
1353 1866
1353 1865
1353 1864
1353 18...

output:

59874

result:

ok single line: '59874'

Test #27:

score: 0
Accepted
time: 74ms
memory: 83048kb

input:

3000 3000 141
200 2617
201 2617
201 2618
202 2618
203 2618
203 2617
202 2617
202 2616
201 2616
201 2615
201 2614
201 2613
200 2613
200 2614
199 2614
198 2614
198 2613
197 2613
197 2614
196 2614
196 2615
196 2616
197 2616
197 2617
197 2618
198 2618
198 2619
197 2619
196 2619
196 2620
195 2620
195 262...

output:

3979414

result:

ok single line: '3979414'

Test #28:

score: 0
Accepted
time: 80ms
memory: 80372kb

input:

3000 2900 26
2187 2667
2187 2666
2188 2666
2188 2667
2189 2667
2189 2666
2189 2665
2189 2664
2188 2664
2188 2663
2189 2663
2190 2663
2190 2662
2189 2662
2189 2661
2190 2661
2190 2660
2190 2659
2190 2658
2191 2658
2191 2657
2191 2656
2190 2656
2189 2656
2189 2657
2190 2657
..#.####.##.####.#.###.####...

output:

32020

result:

ok single line: '32020'

Test #29:

score: 0
Accepted
time: 66ms
memory: 80228kb

input:

2900 3000 258
688 610
688 609
688 608
687 608
686 608
685 608
685 607
685 606
684 606
684 605
685 605
686 605
687 605
687 604
688 604
688 603
689 603
689 602
688 602
687 602
687 603
686 603
686 602
686 601
687 601
687 600
688 600
688 599
687 599
686 599
686 600
685 600
685 599
684 599
684 598
683 59...

output:

27653531

result:

ok single line: '27653531'

Test #30:

score: 0
Accepted
time: 63ms
memory: 82928kb

input:

3000 3000 24
2542 2486
2541 2486
2541 2485
2540 2485
2539 2485
2539 2484
2540 2484
2540 2483
2539 2483
2539 2482
2538 2482
2537 2482
2536 2482
2536 2481
2536 2480
2536 2479
2537 2479
2538 2479
2539 2479
2539 2480
2538 2480
2538 2481
2537 2481
2537 2480
###############################################...

output:

21108

result:

ok single line: '21108'

Test #31:

score: 0
Accepted
time: 364ms
memory: 166048kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

363537285683354

result:

ok single line: '363537285683354'

Test #32:

score: 0
Accepted
time: 419ms
memory: 162452kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

360776872211011

result:

ok single line: '360776872211011'

Test #33:

score: 0
Accepted
time: 434ms
memory: 152848kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

70861586029764531

result:

ok single line: '70861586029764531'

Test #34:

score: 0
Accepted
time: 458ms
memory: 146432kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

358016319444845

result:

ok single line: '358016319444845'

Test #35:

score: -100
Wrong Answer
time: 214ms
memory: 111932kb

input:

3000 3000 100000
1000 1000
1000 1001
1000 1002
1000 1003
1000 1004
1000 1005
1000 1006
1000 1007
1000 1008
1000 1009
1000 1010
1000 1011
1000 1012
1000 1013
1000 1014
1000 1015
1000 1016
1000 1017
1000 1018
1000 1019
1000 1020
1000 1021
1000 1022
1000 1023
1000 1024
1000 1025
1000 1026
1000 1027
100...

output:

24736677174424444

result:

wrong answer 1st lines differ - expected: '25377840152461713', found: '24736677174424444'