QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#348509#1827. Token GameLaStataleBlueAC ✓603ms116840kbC++232.6kb2024-03-09 19:08:142024-03-09 19:08:15

Judging History

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

  • [2024-03-09 19:08:15]
  • 评测
  • 测评结果:AC
  • 用时:603ms
  • 内存:116840kb
  • [2024-03-09 19:08:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N = 301;
vector col(N,vector(N,bitset<N>(0)));
vector sol(N,vector(N,vector(N,0)));

void calc(){
    for(int i=0;i<N;i++){
        vector tmp(N,bitset<N>(0));
        for(int j=0;j<N;j++){
            bitset<N> prec(0);
            
            for(int k=0;k<N;k++){
                int p1=-1,p2=-1;
                
                if(k==i-1 || k==i+1){
                    p1=j;
                }else if(k==i){
                    p1=j-1;
                    p2=j+1;
                }else{
                    p1 = (~(tmp[k]|col[j][k]|prec))._Find_first();
                }
                
                sol[i][j][k]=p1;
                
                if(p1>=0 && p1<N-1){
                    col[j][k][p1]=1;
                    tmp[k][p1]=1;
                    prec[p1]=1;
                }
                if(p2>=0 && p1<N-1){
                    col[j][k][p2]=1;
                    tmp[k][p2]=1;
                    prec[p2]=1;
                }
            }
        }
    }
    /*
    const int X = 5, Y = 7;
    for(int i=0;i<20;i++){
        for(int j=0;j<20;j++){
            if(i==X && j==Y){
                cout<<"X";
            }else if(abs(i-X)+abs(j-Y)==1){
                cout<<"P";
            }else if(abs(i-X)<=1 || abs(j-Y)<=1){
                cout<<"_";
            }else if(sol[X][Y][i]==j){
                cout<<"P";
            }else{
                cout<<"_";
            }
            
            cout<<" ";
        }
        cout<<"\n";
    }*/
}

int check(int X,int Y,int i,int j){
    if(abs(i-X)+abs(j-Y)==1){
        return 1;
    }else if(abs(i-X)<=1 || abs(j-Y)<=1){
        return 0;
    }else if(sol[X][Y][i]==j){
        return 1;
    }else{
        return 0;
    }
}

void solve([[maybe_unused]]int t){
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    x1--;
    y1--;
    x2--;
    y2--;
    
    int ans=0;
    for(int i=x1-1;i>=0;i--){
        if(i==x2 && y1==y2)break;
        ans+=check(i,y1,x2,y2);
    }
    for(int i=y1-1;i>=0;i--){
        if(i==y2 && x1==x2)break;
        ans+=check(x1,i,x2,y2);
    }
    for(int i=x2-1;i>=0;i--){
        if(i==x1 && y1==y2)break;
        ans+=check(x1,y1,i,y2);
    }
    for(int i=y2-1;i>=0;i--){
        if(i==y1 && x1==x2)break;
        ans+=check(x1,y1,x2,i);
    }
    
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    calc();
    
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)solve(i);
    
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 215ms
memory: 116840kb

input:

5
6 6 6 3
6 6 2 2
1 6 3 1
3 6 1 3
6 3 1 5

output:

3
0
1
1
0

result:

ok 5 number(s): "3 0 1 1 0"

Test #2:

score: 0
Accepted
time: 603ms
memory: 116716kb

input:

100000
215 233 28 258
15 243 61 148
172 28 96 37
15 132 62 27
41 186 255 54
145 192 249 263
274 70 185 197
50 101 202 230
256 11 285 19
149 268 163 107
177 201 216 126
65 17 105 263
143 148 2 230
40 128 259 176
183 192 293 169
281 59 240 229
257 157 126 182
161 51 164 14
149 191 227 102
55 14 267 19...

output:

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

result:

ok 100000 numbers