QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#302416#3061. Donut DroneEndlineWA 3ms8184kbC++142.6kb2024-01-10 20:49:142024-01-10 20:49:15

Judging History

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

  • [2024-01-10 20:49:15]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:8184kb
  • [2024-01-10 20:49:14]
  • 提交

answer

/*
 * Author: Endline
 * Time: 2024/01/10 14:15:43
 * File: P4739.cpp
 */
// #pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ll=long long;
const int MAXN=2002;
int n,m,q,nx,ny;
int a[MAXN][MAXN],f[30][MAXN];
inline int move(int x,int y)
{
    int tx1=x-1<1?x+n-1:x-1,tx2=x,tx3=x%n+1,ty=y%m+1;
    int val=max({a[tx1][ty],a[tx2][ty],a[tx3][ty]});
    if(a[tx1][ty]==val)return tx1;
    else if(a[tx2][ty]==val)return tx2;
    else return tx3;
}
struct SegmentTree
{
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    int tr[MAXN<<2][MAXN];
    inline void pushup(int p)
    {
        for(int i=1;i<=n;i++)
            tr[p][i]=tr[rs(p)][tr[ls(p)][i]];
        return;
    }
    void build(int l,int r,int p)
    {
        if(l==r)
        {
            for(int i=1;i<=n;i++)
                tr[p][i]=move(i,l);
            return;
        }
        int mid=l+r>>1;
        build(l,mid,ls(p));build(mid+1,r,rs(p));
        pushup(p);
        return;
    }
    void update(int goal,int s,int t,int p,int k,int val)
    {
        if(s==t)
        {
            a[k][s%m+1]=val;
            tr[p][k-1<1?k+n-1:k-1]=move(k-1<1?k+n-1:k-1,s);
            tr[p][k]=move(k,s);
            tr[p][k%n+1]=move(k%n+1,s);
            return;
        }
        int mid=s+t>>1;
        if(mid>=goal)update(goal,s,mid,ls(p),k,val);
        else update(goal,mid+1,t,rs(p),k,val);
        pushup(p);
        return;
    }
    #undef ls
    #undef rs
}tr;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    cin>>q;
    tr.build(1,m,1);
    nx=ny=1;
    for(int i=1;i<=q;i++)
    {
        string opt;
        cin>>opt;
        if(opt=="move")
        {
            int k;cin>>k;
            while(ny<m&&k)nx=move(nx,ny),ny++,k--;
            if(!k){printf("%d %d\n",nx,ny);continue;}
            nx=move(nx,ny),ny=1,k--;
            if(!k){printf("%d %d\n",nx,ny);continue;}
            for(int j=1;j<=n;j++)
                f[0][j]=tr.tr[1][j];
            for(int j=1;(1<<j)<=k/m;j++)
                for(int l=1;l<=n;l++)
                    f[j][k]=f[j-1][f[j-1][k]];
            int t=k/m;while(t)nx=f[__lg(t)][nx],t-=1<<__lg(t);
            k%=m;
            while(k)nx=move(nx,ny),ny++,k--;
            printf("%d %d\n",nx,ny);
        }
        if(opt=="change")
        {
            int a,b,e;cin>>a>>b>>e;
            tr.update(b-1<1?m:b-1,1,m,1,a,e);
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5848kb

input:

4 4
1 2 9 3
3 5 4 8
4 3 2 7
5 8 1 6
4
move 1
move 1
change 1 4 100
move 1

output:

4 2
1 3
1 4

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 6180kb

input:

3 4
10 20 30 40
50 60 70 80
90 93 95 99
3
move 4
change 2 1 100
move 4

output:

3 1
2 1

result:

ok 2 lines

Test #3:

score: 0
Accepted
time: 2ms
memory: 8068kb

input:

20 30
8 1 7 4 3 1 2 1 5 5 2 7 6 4 7 1 2 9 1 9 9 9 9 6 4 9 1 6 3 10
7 3 5 6 5 3 5 3 1 9 8 8 7 7 6 7 5 10 9 6 5 3 8 2 7 10 6 8 4 3
6 4 3 1 7 7 6 7 2 7 3 6 8 6 3 2 7 8 10 8 6 5 6 10 2 6 5 10 10 9
2 5 10 9 4 9 3 6 10 8 1 7 3 3 7 3 3 6 7 5 1 1 10 6 8 5 4 2 1 8
5 1 2 8 3 4 2 4 4 9 6 3 1 5 9 1 9 3 8 3 7 10...

output:

19 10
18 19
3 24
3 30
3 2
4 3
3 8
7 14
3 21
2 27
3 7
3 8
6 16
5 17
3 24
2 27
3 29
3 8
7 12
6 16
3 22
3 2
7 12
3 19
1 22
4 25
4 3
3 5
7 12
3 20
1 22
2 24
3 2
6 11
3 20
2 24
4 4
3 5
5 10
6 11
4 18
2 21
3 29
3 2
3 5
4 9
6 16
2 25
1 26
2 1
4 6
7 15
2 24
3 2
7 12
3 19
3 28
5 4
9 11
9 12
11 17
10 19
12 21...

result:

ok 1945 lines

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 8184kb

input:

50 50
126812431 909179109 607682292 96000160 425314080 189788877 721251789 103560861 114082307 888028612 277663589 257100764 842807257 327052508 652365304 770138116 384723035 680037089 675501229 509497026 174936063 991259231 761329528 658883078 806406343 741076652 973854314 192609094 398064987 65322...

output:

46 21
46 21
1 49
47 20
46 37
1 42
45 35
50 50
2 17
1 43
2 38
2 47
50 50
2 38
50 50
2 26
2 17
2 34
2 21
4 9
3 6
1 2
1 30
2 40
2 21
2 35
2 17
2 31
2 32
4 9
2 42
3 12
4 8
2 31
1 3
2 15
1 48
1 20
1 30
2 17
49 49
2 14
2 4
1 30
1 29
2 40
2 24
1 27
1 36
1 27
49 47
3 6
2 32
3 41
49 48
2 34
3 41
47 22
49 28
...

result:

wrong answer 89th lines differ - expected: '50 1', found: '0 1'