QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#153216	#1133. Monster Game	Zhou_JK	100 ✓	39ms	4700kb	C++23	4.3kb	2023-08-29 17:45:46	2023-08-29 17:45:47

Judging History

This is the latest submission verdict.

[2023-08-29 17:45:47]
Judged

Verdict: 100
Time: 39ms
Memory: 4700kb

Show

[2023-08-29 17:45:46]
Submitted

answer

#include<iostream>
#include<cstdio>
#include<vector>
#include<functional>
#include<map>
#include<algorithm>
#include"monster.h"
using namespace std;
map<pair<int,int>,bool>book;
bool query(int a,int b)
{
    if(book.count(make_pair(a,b))) return book[make_pair(a,b)];
    else return book[make_pair(a,b)]=Query(a,b);
}
vector<int> Solve(int N)
{
    int n=N;
    vector<int>id(n);
    for(int i=0;i<n;i++)
        id[i]=i;
    function<void(int,int)>merge_sort=[&](int l,int r)
    {
        if(l==r) return;
        int mid=(l+r)/2;
        merge_sort(l,mid);
        merge_sort(mid+1,r);
        vector<int>tmp;
        int p1=l,p2=mid+1;
        while(p1<=mid&&p2<=r)
            if(!query(id[p1],id[p2])) tmp.emplace_back(id[p1]),p1++;
            else tmp.emplace_back(id[p2]),p2++;
        while(p1<=mid)
            tmp.emplace_back(id[p1]),p1++;
        while(p2<=r)
            tmp.emplace_back(id[p2]),p2++;
        for(int i=0;i<(int)tmp.size();i++)
            id[l+i]=tmp[i];
        return;
    };
    merge_sort(0,n-1);
    for(int i=0,j=0;i<n;i=j)
    {
        if(i==0)
        {
            if(query(id[i+2],id[i])) // 012 0321 1032
            {
                if(query(id[i+1],id[i])) //0321 1032
                {
                    for(j=i+3;j<n;j++)
                        if(!query(id[j],id[i])) break;
                    if(j+1<=n) j++;
                    if(query(id[j-1],id[i+1])) reverse(id.begin()+i,id.begin()+i+2),reverse(id.begin()+i+2,id.begin()+j);
                    else reverse(id.begin()+i+1,id.begin()+j);
                    continue;
                }
                else j=i+1;//012
            }
            else //021 102 210 3210
            {
                int cnt=0;
                int k=i+2;
                for(k=i+2;k<n;k++)
                    if(query(id[i],id[k]))
                    {
                        cnt++;
                        if(cnt>=2) break;
                    }
                    else break;
                if(cnt<2) //021 102 210
                {
                    if(i+5<n)
                    {
                        if(!query(id[i+3],id[i+5])&&(!query(id[i+3],id[i])||!query(id[i+3],id[i+1])||!query(id[i+3],id[i+2]))) //210354 021354 102354
                        {
                            if(!query(id[i+3],id[i])) reverse(id.begin()+i,id.begin()+i+3);
                            else if(!query(id[i+3],id[i+1])) reverse(id.begin()+i+1,id.begin()+i+3);
                            else reverse(id.begin()+i,id.begin()+i+2);
                            reverse(id.begin()+i+3,id.begin()+i+6);
                            j=i+6;
                            continue;
                        }
                        else if(!query(id[i+3],id[i+5])&&(!query(id[i+3],id[i])||!query(id[i+3],id[i+1])||!query(id[i+3],id[i+2]))) //210435 021435 102435
                        {
                            if(!query(id[i+3],id[i])) reverse(id.begin()+i,id.begin()+i+3);
                            else if(!query(id[i+3],id[i+1])) reverse(id.begin()+i+1,id.begin()+i+3);
                            else reverse(id.begin()+i,id.begin()+i+2);
                            reverse(id.begin()+i+3,id.begin()+i+6);
                            j=i+6;
                            continue;
                        }
                    }
                    for(j=i+3+2;j<n;j++)
                        if(!query(id[j-2],id[j])) break;
                    if(!query(id[j-1],id[i])) reverse(id.begin()+i,id.begin()+i+3); //210
                    else if(!query(id[j-1],id[i+1])) reverse(id.begin()+i+1,id.begin()+i+3); //021
                    else reverse(id.begin()+i,id.begin()+i+2); //102
                    reverse(id.begin()+i+3,id.begin()+j);
                    continue;
                }
                else //3210
                {
                    for(j=k+1;j<n;j++)
                        if(!query(id[j-2],id[j])) break;
                }
            }
        }
        else
        {
            for(j=i;j<n;j++)
                if(!query(id[j],id[i-1])) break;
            if(j+1<=n) j++;
        }
        reverse(id.begin()+i,id.begin()+j);
    }
    vector<int>s(n);
    for(int i=0;i<n;i++)
        s[id[i]]=i;
    return s;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 2ms

memory: 3808kb

input:

output:

result:

points 1.0 points  1.0

Test #2:

score: 10

Accepted

time: 1ms

memory: 3808kb

input:

output:

result:

points 1.0 points  1.0

Test #3:

score: 10

Accepted

time: 1ms

memory: 4088kb

input:

output:

result:

points 1.0 points  1.0

Test #4:

score: 10

Accepted

time: 1ms

memory: 4096kb

input:

output:

result:

points 1.0 points  1.0

Test #5:

score: 10

Accepted

time: 1ms

memory: 4104kb

input:

output:

result:

points 1.0 points  1.0

Test #6:

score: 10

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

points 1.0 points  1.0

Test #7:

score: 10

Accepted

time: 1ms

memory: 3768kb

input:

output:

Q 0 1
Q 1 2
Q 3 4
Q 4 5
Q 3 5
Q 2 4
Q 1 4
Q 1 5
Q 1 3
Q 5 2
Q 2 5
Q 2 3
Q 3 0
Q 0 2
Q 0 4
F 6
 3 4 1 5 0 2

result:

points 1.0 points  1.0

Test #8:

score: 10

Accepted

time: 1ms

memory: 3804kb

input:

output:

Q 0 1
Q 0 2
Q 1 2
Q 3 4
Q 4 5
Q 0 5
Q 1 5
Q 1 4
Q 1 3
Q 4 0
Q 5 0
Q 3 0
Q 3 5
Q 2 4
F 6
 1 5 4 2 3 0

result:

points 1.0 points  1.0

Test #9:

score: 10

Accepted

time: 0ms

memory: 3800kb

input:

output:

Q 0 1
Q 1 2
Q 3 4
Q 3 5
Q 2 5
Q 1 5
Q 1 3
Q 0 3
Q 0 4
Q 5 2
Q 3 2
Q 4 1
F 6
 5 3 1 2 4 0

result:

points 1.0 points  1.0

Test #10:

score: 10

Accepted

time: 1ms

memory: 3728kb

input:

output:

Q 0 1
Q 2 3
Q 0 3
Q 0 2
Q 1 2
Q 4 5
Q 4 6
Q 5 6
Q 3 4
Q 3 5
Q 0 5
Q 2 5
Q 2 6
Q 1 6
Q 0 4
Q 4 0
Q 5 4
Q 5 3
Q 5 0
Q 2 4
Q 6 5
Q 1 5
F 7
 0 5 3 1 2 4 6

result:

points 1.0 points  1.0

Test #11:

score: 10

Accepted

time: 1ms

memory: 3820kb

input:

output:

Q 0 1
Q 2 3
Q 0 3
Q 1 3
Q 4 5
Q 5 6
Q 0 6
Q 0 5
Q 0 4
Q 4 6
Q 6 4
Q 6 0
Q 1 6
Q 1 5
Q 3 0
Q 2 0
F 7
 4 3 5 6 2 0 1

result:

points 1.0 points  1.0

Test #12:

score: 10

Accepted

time: 1ms

memory: 3776kb

input:

output:

Q 0 1
Q 2 3
Q 0 3
Q 1 3
Q 1 2
Q 4 5
Q 4 6
Q 5 6
Q 0 4
Q 0 5
Q 3 5
Q 1 5
Q 2 5
Q 3 4
Q 4 3
Q 4 1
Q 1 4
Q 1 0
Q 2 4
Q 5 1
Q 6 1
F 7
 1 4 3 0 2 6 5

result:

points 1.0 points  1.0

Test #13:

score: 10

Accepted

time: 1ms

memory: 3796kb

input:

output:

Q 0 1
Q 2 3
Q 0 3
Q 0 2
Q 1 2
Q 4 5
Q 6 7
Q 5 7
Q 5 6
Q 4 6
Q 3 7
Q 3 5
Q 3 6
Q 0 6
Q 1 6
Q 2 6
Q 0 7
Q 0 5
Q 1 3
Q 2 1
Q 6 1
Q 4 1
F 8
 2 4 7 3 5 0 6 1

result:

points 1.0 points  1.0

Test #14:

score: 10

Accepted

time: 2ms

memory: 3808kb

input:

output:

Q 0 1
Q 2 3
Q 1 2
Q 1 3
Q 0 3
Q 4 5
Q 6 7
Q 4 6
Q 5 6
Q 5 7
Q 2 4
Q 2 6
Q 1 6
Q 0 6
Q 3 6
Q 3 5
Q 3 7
Q 1 4
Q 4 1
Q 4 0
Q 0 5
Q 6 3
Q 5 4
Q 5 2
Q 3 0
Q 7 0
F 8
 5 1 2 7 0 3 4 6

result:

points 1.0 points  1.0

Test #15:

score: 10

Accepted

time: 1ms

memory: 3808kb

input:

output:

Q 0 1
Q 2 3
Q 1 2
Q 1 3
Q 0 3
Q 4 5
Q 6 7
Q 4 6
Q 4 7
Q 2 6
Q 1 6
Q 1 7
Q 0 7
Q 3 7
Q 6 2
Q 0 2
Q 0 6
Q 3 6
Q 7 3
Q 4 3
Q 5 3
F 8
 1 2 0 4 6 5 3 7

result:

points 1.0 points  1.0

Test #16:

score: 10

Accepted

time: 2ms

memory: 3896kb

input:

output:

result:

points 1.0 points  1.0

Test #17:

score: 10

Accepted

time: 8ms

memory: 4156kb

input:

output:

result:

points 1.0 points  1.0

Test #18:

score: 10

Accepted

time: 2ms

memory: 3872kb

input:

output:

result:

points 1.0 points  1.0

Test #19:

score: 10

Accepted

time: 3ms

memory: 3848kb

input:

output:

result:

points 1.0 points  1.0

Test #20:

score: 10

Accepted

time: 11ms

memory: 4156kb

input:

output:

result:

points 1.0 points  1.0

Test #21:

score: 10

Accepted

time: 1ms

memory: 3812kb

input:

output:

result:

points 1.0 points  1.0

Test #22:

score: 10

Accepted

time: 1ms

memory: 3812kb

input:

output:

result:

points 1.0 points  1.0

Test #23:

score: 10

Accepted

time: 0ms

memory: 3820kb

input:

output:

Q 0 1
Q 1 2
Q 3 4
Q 4 5
Q 2 5
Q 1 5
Q 0 5
Q 0 2
Q 2 0
Q 5 3
Q 3 2
F 6
 0 1 2 3 4 5

result:

points 1.0 points  1.0

Test #24:

score: 10

Accepted

time: 1ms

memory: 4028kb

input:

output:

Q 0 1
Q 2 3
Q 1 3
Q 0 3
Q 4 5
Q 5 6
Q 1 6
Q 0 6
Q 3 6
Q 2 6
Q 3 1
Q 2 1
Q 2 0
Q 6 3
Q 5 3
Q 4 3
F 7
 0 1 2 3 4 5 6

result:

points 1.0 points  1.0

Test #25:

score: 10

Accepted

time: 1ms

memory: 4100kb

input:

output:

Q 0 1
Q 2 3
Q 1 3
Q 0 3
Q 4 5
Q 6 7
Q 5 7
Q 4 7
Q 1 5
Q 0 5
Q 3 5
Q 2 5
Q 3 1
Q 2 1
Q 2 0
Q 5 3
Q 4 3
Q 7 5
Q 6 5
F 8
 0 1 2 3 4 5 6 7

result:

points 1.0 points  1.0

Test #26:

score: 10

Accepted

time: 10ms

memory: 3816kb

input:

output:

result:

points 1.0 points  1.0

Test #27:

score: 10

Accepted

time: 1ms

memory: 4092kb

input:

output:

result:

points 1.0 points  1.0

Test #28:

score: 10

Accepted

time: 1ms

memory: 3804kb

input:

output:

result:

points 1.0 points  1.0

Test #29:

score: 10

Accepted

time: 1ms

memory: 4104kb

input:

output:

Q 0 1
Q 0 2
Q 3 4
Q 3 5
Q 2 5
Q 2 3
Q 0 3
Q 0 4
Q 4 5
Q 4 2
Q 1 2
F 6
 5 4 3 2 1 0

result:

points 1.0 points  1.0

Test #30:

score: 10

Accepted

time: 1ms

memory: 3748kb

input:

output:

Q 0 1
Q 2 3
Q 0 2
Q 0 3
Q 4 5
Q 4 6
Q 2 6
Q 2 4
Q 2 5
Q 5 6
Q 6 5
Q 6 2
Q 2 0
Q 3 6
Q 3 4
Q 1 2
F 7
 6 5 4 3 2 1 0

result:

points 1.0 points  1.0

Test #31:

score: 10

Accepted

time: 0ms

memory: 4100kb

input:

output:

Q 0 1
Q 2 3
Q 0 2
Q 0 3
Q 4 5
Q 6 7
Q 4 6
Q 4 7
Q 2 6
Q 2 7
Q 2 4
Q 2 5
Q 7 6
Q 5 6
Q 5 7
Q 3 4
Q 1 2
F 8
 7 6 5 4 3 2 1 0

result:

points 1.0 points  1.0

Test #32:

score: 10

Accepted

time: 1ms

memory: 4120kb

input:

output:

result:

points 1.0 points  1.0

Subtask #2:

score: 15

Accepted

Test #33:

score: 15

Accepted

time: 31ms

memory: 4416kb

input:

output:

result:

points 1.0 points  1.0

Test #34:

score: 15

Accepted

time: 13ms

memory: 4404kb

input:

output:

result:

points 1.0 points  1.0

Test #35:

score: 15

Accepted

time: 16ms

memory: 4408kb

input:

output:

result:

points 1.0 points  1.0

Test #36:

score: 15

Accepted

time: 9ms

memory: 4696kb

input:

output:

result:

points 1.0 points  1.0

Test #37:

score: 15

Accepted

time: 30ms

memory: 4404kb

input:

output:

result:

points 1.0 points  1.0

Test #38:

score: 15

Accepted

time: 36ms

memory: 4416kb

input:

output:

result:

points 1.0 points  1.0

Test #39:

score: 15

Accepted

time: 28ms

memory: 4408kb

input:

output:

result:

points 1.0 points  1.0

Test #40:

score: 15

Accepted

time: 16ms

memory: 4700kb

input:

output:

result:

points 1.0 points  1.0

Test #41:

score: 15

Accepted

time: 22ms

memory: 4400kb

input:

output:

result:

points 1.0 points  1.0

Test #42:

score: 15

Accepted

time: 6ms

memory: 4672kb

input:

output:

result:

points 1.0 points  1.0

Test #43:

score: 15

Accepted

time: 10ms

memory: 4256kb

input:

output:

result:

points 1.0 points  1.0

Test #44:

score: 15

Accepted

time: 16ms

memory: 4156kb

input:

output:

result:

points 1.0 points  1.0

Subtask #3:

score: 75

Accepted

Test #45:

score: 75

Accepted

time: 22ms

memory: 4404kb

input:

output:

result:

points 1.0 points  1.0

Test #46:

score: 75

Accepted

time: 7ms

memory: 4696kb

input:

output:

result:

points 1.0 points  1.0

Test #47:

score: 75

Accepted

time: 20ms

memory: 4408kb

input:

output:

result:

points 1.0 points  1.0

Test #48:

score: 75

Accepted

time: 20ms

memory: 4688kb

input:

output:

result:

points 1.0 points  1.0

Test #49:

score: 75

Accepted

time: 5ms

memory: 4412kb

input:

output:

result:

points 1.0 points  1.0

Test #50:

score: 75

Accepted

time: 24ms

memory: 4396kb

input:

output:

result:

points 1.0 points  1.0

Test #51:

score: 75

Accepted

time: 11ms

memory: 4308kb

input:

output:

result:

points 1.0 points  1.0

Test #52:

score: 75

Accepted

time: 17ms

memory: 4672kb

input:

output:

result:

points 1.0 points  1.0

Test #53:

score: 75

Accepted

time: 23ms

memory: 4436kb

input:

output:

result:

points 1.0 points  1.0

Test #54:

score: 75

Accepted

time: 23ms

memory: 4440kb

input:

output:

result:

points 1.0 points  1.0

Test #55:

score: 75

Accepted

time: 38ms

memory: 4408kb

input:

output:

result:

points 1.0 points  1.0

Test #56:

score: 75

Accepted

time: 14ms

memory: 4648kb

input:

output:

result:

points 1.0 points  1.0

Test #57:

score: 75

Accepted

time: 39ms

memory: 4256kb

input:

output:

result:

points 1.0 points  1.0

Test #58:

score: 75

Accepted

time: 22ms

memory: 4308kb

input:

output:

result:

points 1.0 points  1.0

Test #59:

score: 75

Accepted

time: 11ms

memory: 4272kb

input:

output:

result:

points 1.0 points  1.0

Test #60:

score: 75

Accepted

time: 4ms

memory: 4440kb

input:

output:

result:

points 1.0 points  1.0

Test #61:

score: 75

Accepted

time: 11ms

memory: 4376kb

input:

output:

result:

points 1.0 points  1.0

Test #62:

score: 75

Accepted

time: 5ms

memory: 4440kb

input:

output:

result:

points 1.0 points  1.0