QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33165 | #1827. Token Game | bulijiojiodibuliduo# | AC ✓ | 471ms | 124852kb | C++ | 3.1kb | 2022-05-29 05:44:19 | 2022-05-29 05:44:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
using u64 = unsigned long long;
const int M=301;
//bool dp2[101][101][101][101];
const int M2=(M/64+1)*64;
bitset<M2> f1[M][M],f2[M][M],sy[M][M],sx[M][M];
int losp[M][M][M];
int losp2[M][M];
int main() {
int N=300;
memset(losp,0x10,sizeof(losp));
memset(losp2,0x10,sizeof(losp2));
for (int x1=0;x1<N;x1++) for (int x2=0;x2<N;x2++) {
if (x1!=x2) {
bitset<M2> mark,msk;
rep(y1,0,N) {
msk=mark|f2[x1][y1]|f1[x2][y1];
//printf("f1 %llu\n",a[0]);
u64* a=(u64*)((void*)&msk);
if (sy[x1][x2][y1]) {
a[y1/64]|=1ull<<(y1%64);
//printf("upd %d %d %d %llu\n",x1,x2,y1,a[0]);
}
int y2=N;
//printf("%d %d\n",a,&msk);
for (int i=0;i<=N/64;i++) {
//printf("fuck %llu\n",a[i]);
if (~a[i]) { y2=i*64+__builtin_ctzll(~a[i]); break; }
}
if (y2>=N) continue;
assert(msk[y2]==0);
mark[y2]=1;
losp[x1][x2][y1]=y2;
//printf("cnm %d %d %d %d\n",x1,x2,y1,y2);
if (x2<x1) assert(losp[x1][x2][y1]==losp[x2][x1][y1]);
if (y1==y2) {
int p;
p=x1;
while (p+1<N&&mp(p+1,y1)!=mp(x2,y2))
++p,sy[p][x2][y1]=1;
p=x2;
while (p+1<N&&mp(x1,y1)!=mp(p+1,y2))
++p,sy[x1][p][y1]=1;
} else {
f1[x2][y1][y2]=1;
f2[x1][y1][y2]=1;
}
}
} else {
for (int y1=0;y1<N;y1++) for (int y2=0;y2<N;y2++) {
if (mp(x1,y1)==mp(x2,y2)) continue;
bool vs=0;
vs=sx[x1][y1][y2]|f2[x1][y1][y2]|f1[x2][y1][y2];
if (vs==0) {
//printf("cnm2 %d %d %d %d\n",x1,x2,y1,y2);
if (y1<y2) losp2[x1][y1]=y2;
else losp[x1][x1][y1]=y2;
f1[x2][y1][y2]=1;
f2[x1][y1][y2]=1;
int p;
p=y1;
while (p+1<N&&mp(x1,p+1)!=mp(x2,y2))
++p,sx[x2][p][y2]=1;
p=y2;
while (p+1<N&&mp(x1,y1)!=mp(x2,p+1))
++p,sx[x2][y1][p]=1;
}
}
}
}
int q;
scanf("%d",&q);
auto query=[&](int x1,int y1,int x2,int y2) {
if (x1!=x2||y2<y1) return y2>losp[x1][x2][y1]?1:0;
else return y2>losp2[x1][y1]?1:0;
};
rep(i,0,q) {
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
--x1; --y1; --x2; --y2;
printf("%d\n",query(x1,y1,x2,y2)+query(y1,x1,y2,x2)+query(x2,y2,x1,y1)+query(y2,x2,y1,x1));
//printf("cnm %d %d %d %d\n",query(x1,y1,x2,y2),query(y1,x1,y2,x2),query(x2,y2,x1,y1),query(y2,x2,y1,x1));
}
/* rep(x1,0,N) rep(x2,0,N) {
for (int y1=0;y1<N;y1++) for (int y2=0;y2<N;y2++) {
assert(dp[x1][x2][y1][y2]==dp2[x1][x2][y1][y2]);
}
}*/
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 440ms
memory: 124852kb
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: 471ms
memory: 124720kb
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