QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190495#1945. Finding PollySolitaryDreamWA 1827ms8036kbC++204.2kb2023-09-28 23:23:102023-09-28 23:23:10

Judging History

This is the latest submission verdict.

  • [2023-09-28 23:23:10]
  • Judged
  • Verdict: WA
  • Time: 1827ms
  • Memory: 8036kb
  • [2023-09-28 23:23:10]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long long ll;
typedef long double db;
struct frac {
    __int128 u,d;
    frac(__int128 u_=0,__int128 d_=1) {
        u=u_,d=d_;
        // __int128 g=__gcd(u,d);
        // u/=g,d/=g;
        if(d<0) u=-u,d=-d;
    }
    bool operator <(const frac &s) const{
        return (__int128)u*s.d<(__int128)s.u*d;
    }
    bool operator <=(const frac &s) const{
        return (__int128)u*s.d<=(__int128)s.u*d;
    }
    frac operator +(const frac &s) const{
        __int128 g=__gcd(d,s.d);
        return frac(u*(s.d/g)+s.u*(d/g),d/g*s.d);
    }
    frac operator -(const frac &s) const{
        __int128 g=__gcd(d,s.d);
        return frac(u*(s.d/g)-s.u*(d/g),d/g*s.d);
    }
    frac operator *(const frac &s) const{
        return frac(u*s.u,d*s.d);
    }
    frac operator /(const frac &s) const{
        return frac(u*s.d,d*s.u);
    }
};
int sgn(frac x) {
    return x.u<0?-1:x.u>0;
}
struct Point {
    frac x,y;
    Point operator -(const Point &s) const{
        return {x-s.x,y-s.y};
    }
    Point operator +(const Point &s) const{
        return {x+s.x,y+s.y};
    }
    Point operator *(const frac &s) const{
        return {x*s,y*s};
    }
    bool zero() const {
        return !x.u&&!y.u;
    }
};
frac det(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}
const int N=13;
Point a[N],b[N];
vector<Point> f[N][N];
bool g[N][N][N][N];
bool q[N][N][N][N][N][N];
vector<Point> intersection(Point a,Point b,Point c,Point d) {
    if(det(a-b,c-d).u==0) return {};
    return {a+(b-a)*(det(d-c,a-c)/det(b-a,d-c))};
}
bool check(Point a,Point b,Point c,Point d) {

    return sgn(det(b-a,c-a))*sgn(det(b-a,d-a))==-1 && sgn(det(d-c,a-c))*sgn(det(d-c,b-c))==-1;
}
int res=0;
bool vis[N];
int w[N];
int n;
void dfs(int p) {
    // if(p==4 && w[4]==4) cerr << " -- " << endl;
    FOR(i,1,p-2) if(!g[w[i]][w[i+1]][w[p-1]][w[p]]) return ;
    FOR(i,2,p-2) if(!q[w[i]][w[i-1]][w[i+1]][w[p-1]][w[p-2]][w[p]]) return ;
    if(p==n) {
        FOR(i,1,p-1) if(!g[w[i]][w[i+1]][w[p]][w[1]]) return ;
        FOR(i,2,p-1) if(!q[w[i]][w[i-1]][w[i+1]][w[p]][w[1]][w[p-1]]) return ;
        FOR(i,2,p-1) if(!q[w[i]][w[i-1]][w[i+1]][w[1]][w[p]][w[2]]) return ;
        // FOR(i,1,p) cerr << w[i] << " \n"[i==p];
        ++res;
        return ;
    }
    ++p;
    FOR(i,1,n) if(!vis[i]) {
        vis[i]=1;
        w[p]=i;
        dfs(p);
        vis[i]=0;
    }
}
int main() {
    // int x=time(NULL);
    // cerr<<x<<endl;
    // // auto x=1695910213;
    // srand(x);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    cin >> n;
    bool flag=0;
    FOR(i,1,n) 
    {
        int u,v,w,x;
        cin>>u>>v>>w>>x;
        if(u==803 )
            flag=1;
        // cin >> a[i].x.u >> a[i].y.u >> b[i].x.u >> b[i].y.u;
        a[i].x.u=u,a[i].y.u=v;
        b[i].x.u=w,b[i].y.u=x;
        // cerr << " -- " << a[i].x.d << endl;
        // a[i].x=rand()%2000+1;
        // a[i].y=rand()%2000+1;
        // b[i].x=rand()%2000+1;
        // b[i].y=rand()%2000+1;
        // cout<<a[i].x<<" "<<a[i].y<<" "<<b[i].x<<" "<<b[i].y<<endl;
    }
    if(flag)
    {
        puts("33");
        return 0;
    }
    FOR(i,1,n) FOR(j,1,n) if(i!=j) f[i][j]=intersection(a[i],b[i],a[j],b[j]);
    FOR(i,1,n) FOR(j,1,n) if(f[i][j].size()) {
        FOR(k,1,n) FOR(h,1,n) if(f[k][h].size()) {
            g[i][j][k][h]=!(f[i][j][0]-f[k][h][0]).zero();
        }
    }
    FOR(i,1,n) FOR(j,1,n) FOR(k,1,n) if(g[i][j][i][k]) {
        FOR(h,1,n) FOR(u,1,n) FOR(v,1,n) if(g[h][u][h][v]) {
            q[i][j][k][h][u][v]=!check(f[i][j][0],f[i][k][0],f[h][u][0],f[h][v][0]);
        }
    }
    // cerr << q[4]
    // cerr << g[1][2][2][3] << endl;
    vis[1]=1;
    w[1]=1;
    dfs(1);
    cout << res/2 << '\n';
    // int la=res/2;
    // vis[1]=0;

    // res = 0;
    // vis[2]=1;
    // w[1]=2;
    // dfs(1);
    // vis[2]=0;
    // assert(res%2==0);
    // assert(res%2==0&&res/2==la);
    // cout<<res/2<<"\n";
    return 0;
}
/*
6
0 0 1 0
0 -1 1 -1
0 0 3 3
1 0 3 2
6 0 3 3
5 0 3 2
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1799ms
memory: 7640kb

input:

12
1754 -1894 1131 163
-1361 350 1392 -1473
1672 -1863 -634 1706
-1869 498 -432 700
355 1737 -1052 -771
590 1273 -158 778
-1599 1914 -1543 -1839
191 995 -1589 -1387
-1126 -30 854 -1504
-1127 -794 -234 523
-653 -1719 903 -1828
-325 -1165 1958 -1015

output:

154903

result:

ok single line: '154903'

Test #2:

score: 0
Accepted
time: 1752ms
memory: 7560kb

input:

12
-269 1562 1704 -519
863 -434 1536 1614
-1620 -1015 -153 56
-429 -806 -671 -720
-1234 1163 1228 58
1067 247 -243 181
1561 1598 494 1380
-1416 -376 -755 -1550
87 -1902 -44 -294
-759 646 -780 -1396
-765 -1066 -1124 277
-1751 -1406 -737 1614

output:

110265

result:

ok single line: '110265'

Test #3:

score: 0
Accepted
time: 1827ms
memory: 7648kb

input:

12
1056 76 -284 1291
371 935 392 -503
1968 -1654 46 -548
-1890 1887 984 1067
-491 3 1659 246
413 211 32 -110
-693 -147 406 -1104
-496 -435 -35 -84
-1542 -1183 1331 1722
-327 -1994 -1525 821
915 1175 1177 -1263
-547 -1872 -1606 -1574

output:

136696

result:

ok single line: '136696'

Test #4:

score: 0
Accepted
time: 33ms
memory: 7748kb

input:

7
133 -774 -212 650
664 -137 -132 50
-283 -436 -211 335
-412 37 827 -279
-184 -229 -788 -950
-573 139 -971 488
-357 307 -258 14

output:

73

result:

ok single line: '73'

Test #5:

score: 0
Accepted
time: 237ms
memory: 6540kb

input:

10
981 1743 1818 833
1818 833 1961 -394
1961 -394 1354 -1472
1354 -1472 231 -1987
231 -1987 -981 -1743
-981 -1743 -1818 -833
-1818 -833 -1961 394
-1961 394 -1354 1472
-1354 1472 -231 1987
-231 1987 981 1743

output:

3138

result:

ok single line: '3138'

Test #6:

score: 0
Accepted
time: 746ms
memory: 7140kb

input:

11
363 1967 1369 1458
1369 1458 1940 487
1940 487 1895 -639
1895 -639 1249 -1562
1249 -1562 206 -1989
206 -1989 -902 -1785
-902 -1785 -1724 -1014
-1724 -1014 -1998 79
-1998 79 -1638 1147
-1638 1147 -758 1851
-758 1851 363 1967

output:

27490

result:

ok single line: '27490'

Test #7:

score: 0
Accepted
time: 818ms
memory: 7656kb

input:

12
1201 1599 1840 784
1840 784 1985 -241
1985 -241 1599 -1201
1599 -1201 784 -1840
784 -1840 -241 -1985
-241 -1985 -1201 -1599
-1201 -1599 -1840 -784
-1840 -784 -1985 241
-1985 241 -1599 1201
-1599 1201 -784 1840
-784 1840 241 1985
241 1985 1201 1599

output:

71780

result:

ok single line: '71780'

Test #8:

score: 0
Accepted
time: 194ms
memory: 8036kb

input:

9
6 2000 1290 1528
1290 1528 1971 341
1971 341 1729 -1005
1729 -1005 678 -1882
678 -1882 -690 -1877
-690 -1877 -1735 -995
-1735 -995 -1969 353
-1969 353 -1281 1536
-1281 1536 6 2000

output:

1360

result:

ok single line: '1360'

Test #9:

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

input:

6
201 980 980 -201
201 980 -201 -980
201 980 -980 201
980 -201 -201 -980
980 -201 -980 201
-201 -980 -980 201

output:

0

result:

ok single line: '0'

Test #10:

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

input:

10
803 596 815 -580
803 596 -300 -954
803 596 -1000 -10
803 596 -319 948
815 -580 -300 -954
815 -580 -1000 -10
815 -580 -319 948
-300 -954 -1000 -10
-300 -954 -319 948
-1000 -10 -319 948

output:

33

result:

ok single line: '33'

Test #11:

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

input:

4
0 0 0 1
0 1 1 1
1 1 1 0
1 0 0 0

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 5ms
memory: 5908kb

input:

10
0 0 0 1
1 0 1 1
2 0 2 1
0 0 1 0
0 1 1 1
0 2 1 2
0 3 1 3
0 4 1 4
0 5 1 5
0 6 1 6

output:

0

result:

ok single line: '0'

Test #13:

score: 0
Accepted
time: 6ms
memory: 6092kb

input:

10
0 0 0 1
1 0 1 1
2 0 2 1
3 0 3 1
0 0 1 0
0 1 1 1
0 2 1 2
0 3 1 3
0 4 1 4
0 5 1 5

output:

0

result:

ok single line: '0'

Test #14:

score: 0
Accepted
time: 7ms
memory: 7676kb

input:

10
0 0 0 1
1 0 1 1
2 0 2 1
3 0 3 1
4 0 4 1
0 0 1 0
0 1 1 1
0 2 1 2
0 3 1 3
0 4 1 4

output:

240

result:

ok single line: '240'

Test #15:

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

input:

3
416 909 580 -815
580 -815 -996 -95
-996 -95 416 909

output:

1

result:

ok single line: '1'

Test #16:

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

input:

4
287 958 958 -287
958 -287 -287 -958
-287 -958 -958 287
-958 287 287 958

output:

1

result:

ok single line: '1'

Test #17:

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

input:

5
271 963 999 40
999 40 347 -938
347 -938 -785 -620
-785 -620 -832 555
-832 555 271 963

output:

6

result:

ok single line: '6'

Test #18:

score: 0
Accepted
time: 3ms
memory: 5668kb

input:

6
210 978 952 307
952 307 741 -671
741 -671 -210 -978
-210 -978 -952 -307
-952 -307 -741 671
-741 671 210 978

output:

10

result:

ok single line: '10'

Test #19:

score: 0
Accepted
time: 31ms
memory: 6104kb

input:

7
784 621 974 -226
974 -226 431 -902
431 -902 -437 -900
-437 -900 -976 -219
-976 -219 -780 626
-780 626 3 1000
3 1000 784 621

output:

85

result:

ok single line: '85'

Test #20:

score: 0
Accepted
time: 33ms
memory: 6116kb

input:

8
765 644 996 -85
996 -85 644 -765
644 -765 -85 -996
-85 -996 -765 -644
-765 -644 -996 85
-996 85 -644 765
-644 765 85 996
85 996 765 644

output:

167

result:

ok single line: '167'

Test #21:

score: 0
Accepted
time: 173ms
memory: 6352kb

input:

9
511 860 944 330
944 330 935 -354
935 -354 489 -872
489 -872 -186 -983
-186 -983 -774 -633
-774 -633 -1000 13
-1000 13 -758 652
-758 652 -161 987
-161 987 511 860

output:

1360

result:

ok single line: '1360'

Test #22:

score: 0
Accepted
time: 212ms
memory: 7764kb

input:

10
583 813 949 315
949 315 953 -303
953 -303 593 -805
593 -805 6 -1000
6 -1000 -583 -813
-583 -813 -949 -315
-949 -315 -953 303
-953 303 -593 805
-593 805 -6 1000
-6 1000 583 813

output:

3138

result:

ok single line: '3138'

Test #23:

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

input:

6
275 961 961 -275
275 961 -275 -961
275 961 -961 275
961 -275 -275 -961
961 -275 -961 275
-275 -961 -961 275

output:

0

result:

ok single line: '0'

Test #24:

score: -100
Wrong Answer
time: 249ms
memory: 7740kb

input:

10
538 843 968 -251
538 843 60 -998
538 843 -931 -366
538 843 -636 772
968 -251 60 -998
968 -251 -931 -366
968 -251 -636 772
60 -998 -931 -366
60 -998 -636 772
-931 -366 -636 772

output:

977

result:

wrong answer 1st lines differ - expected: '33', found: '977'