oj.uz

Submission #420628

# Submission time Handle Problem Language Result Execution time Memory
420628 2021-06-08T13:02:14 Z zaneyu Monster Game (JOI21_monster) C++17
93 / 100
 186 ms 1680 KB 
/*input
2
4
bbcb
aada
aada
3
abc
bbb
bbb

*/
#include "monster.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("Ofast")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (ll)x.size()
const ll maxn=2e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e17;
const int INF=0x3f3f3f3f;
const ll MOD2=3006703054056749LL;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll mult(ll a,ll b){
	ll res=0;
	while(b){
		if(b&1) res+=a,res%=MOD;
		a+=a;
		a%=MOD; 
		b>>=1;
	}
	return res;
}
ll mypow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=mult(res,a);
		a=mult(a,a);
		b/=2;
	}
	return res;
}
int tmp[maxn],arr[maxn];
map<pii,bool> mp;
bool cmp(int a,int b){
    if(mp.count({a,b})) return mp[{a,b}];
    mp[{a,b}]=Query(a,b);
    mp[{b,a}]=1-mp[{a,b}];
    return mp[{a,b}];
}
void srt(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    srt(l,mid);
    srt(mid+1,r);
    int p1=l,p2=mid+1,p=l;
    while(p1<=mid and p2<=r){
        if(cmp(arr[p1],arr[p2])) tmp[p++]=arr[p1++];
        else tmp[p++]=arr[p2++];
    }
    while(p1<=mid) tmp[p++]=arr[p1++];
    while(p2<=r) tmp[p++]=arr[p2++];
    for(int i=l;i<=r;i++) arr[i]=tmp[i]; 
}
vector<int> Solve(int n) {
    REP(i,n) arr[i]=i;
    srt(0,n-1);
    //REP(i,n) cout<<arr[i]<<' ';
    vector<int> ans(n);
    vector<int> v;
    REP1(i,n-1){
        if(!cmp(arr[0],arr[i])){
            v.pb(i);
        }
    }
    int mx=0;
    if(sz(v)==1){
        if(cmp(arr[1],arr[v[0]])){
            if(v[0]==2){
                mx=0;
                for(int i=3;i<n;i++){
                    if(!cmp(arr[2],arr[i])){
                        mx=1;
                        break;
                    }
                }
            }
            else mx=1;
        }
        else{
            mx=0;
        }
    }
    else{
        mx=v[sz(v)-2];
    }
    int cur=n-1;
    for(int i=mx;i>=0;i--){
        ans[arr[i]]=(cur--);
    }
    int p=0;
    v.clear();
    for(int i=mx+1;i<n;i++){
        v.pb(i);
        if(!cmp(arr[p],arr[i])){
            reverse(ALL(v));
            p=v.back();
            for(auto x:v) ans[arr[x]]=(cur--);
            v.clear();        
        }
    }
    //for(auto x:ans) cout<<x<<' ';
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 1 ms 200 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 21 ms 468 KB Output is correct
17 Correct 25 ms 372 KB Output is correct
18 Correct 10 ms 432 KB Output is correct
19 Correct 10 ms 472 KB Output is correct
20 Correct 11 ms 468 KB Output is correct
21 Correct 0 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 200 KB Output is correct
26 Correct 13 ms 384 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 9 ms 408 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct
8 Correct 1 ms 200 KB Output is correct
9 Correct 1 ms 200 KB Output is correct
10 Correct 1 ms 200 KB Output is correct
11 Correct 1 ms 200 KB Output is correct
12 Correct 1 ms 200 KB Output is correct
13 Correct 1 ms 200 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 200 KB Output is correct
16 Correct 21 ms 468 KB Output is correct
17 Correct 25 ms 372 KB Output is correct
18 Correct 10 ms 432 KB Output is correct
19 Correct 10 ms 472 KB Output is correct
20 Correct 11 ms 468 KB Output is correct
21 Correct 0 ms 200 KB Output is correct
22 Correct 1 ms 200 KB Output is correct
23 Correct 1 ms 200 KB Output is correct
24 Correct 1 ms 200 KB Output is correct
25 Correct 1 ms 200 KB Output is correct
26 Correct 13 ms 384 KB Output is correct
27 Correct 1 ms 200 KB Output is correct
28 Correct 1 ms 200 KB Output is correct
29 Correct 1 ms 200 KB Output is correct
30 Correct 1 ms 200 KB Output is correct
31 Correct 1 ms 200 KB Output is correct
32 Correct 9 ms 408 KB Output is correct
33 Correct 152 ms 1568 KB Output is correct
34 Correct 69 ms 1532 KB Output is correct
35 Correct 99 ms 1628 KB Output is correct
36 Correct 186 ms 1576 KB Output is correct
37 Correct 94 ms 1532 KB Output is correct
38 Correct 115 ms 1528 KB Output is correct
39 Correct 128 ms 1532 KB Output is correct
40 Correct 162 ms 1564 KB Output is correct
41 Correct 102 ms 1576 KB Output is correct
42 Correct 130 ms 1680 KB Output is correct
43 Correct 69 ms 1116 KB Output is correct
44 Correct 73 ms 1072 KB Output is correct

Subtask #3
68.0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 119 ms 1576 KB Partially correct
2 Partially correct 142 ms 1616 KB Partially correct
3 Partially correct 106 ms 1464 KB Partially correct
4 Partially correct 112 ms 1624 KB Partially correct
5 Partially correct 97 ms 1584 KB Partially correct
6 Correct 99 ms 1356 KB Output is correct
7 Correct 101 ms 1304 KB Output is correct
8 Partially correct 155 ms 1476 KB Partially correct
9 Partially correct 111 ms 1456 KB Partially correct
10 Partially correct 146 ms 1676 KB Partially correct
11 Partially correct 117 ms 1528 KB Partially correct
12 Partially correct 148 ms 1524 KB Partially correct
13 Correct 93 ms 1368 KB Output is correct
14 Correct 85 ms 1316 KB Output is correct
15 Correct 85 ms 1212 KB Output is correct
16 Correct 83 ms 1040 KB Output is correct
17 Correct 82 ms 1192 KB Output is correct
18 Correct 92 ms 1460 KB Output is correct