oj.uz

Submission #420587

# Submission time Handle Problem Language Result Execution time Memory
420587 2021-06-08T12:49:42 Z zaneyu Monster Game (JOI21_monster) C++17
73 / 100
 136 ms 1824 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;
            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
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 256 KB Output is correct
5 Incorrect 0 ms 200 KB Wrong Answer [3]
6 Halted 0 ms 0 KB -

Subtask #2
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 256 KB Output is correct
5 Incorrect 0 ms 200 KB Wrong Answer [3]
6 Halted 0 ms 0 KB -

Subtask #3
73.0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 135 ms 1524 KB Partially correct
2 Partially correct 112 ms 1536 KB Partially correct
3 Partially correct 135 ms 1540 KB Partially correct
4 Partially correct 134 ms 1560 KB Partially correct
5 Partially correct 132 ms 1464 KB Partially correct
6 Correct 87 ms 1364 KB Output is correct
7 Correct 116 ms 1352 KB Output is correct
8 Partially correct 114 ms 1520 KB Partially correct
9 Partially correct 136 ms 1480 KB Partially correct
10 Partially correct 128 ms 1824 KB Partially correct
11 Partially correct 120 ms 1460 KB Partially correct
12 Partially correct 106 ms 1596 KB Partially correct
13 Correct 69 ms 1456 KB Output is correct
14 Correct 86 ms 1360 KB Output is correct
15 Correct 65 ms 1056 KB Output is correct
16 Correct 87 ms 1252 KB Output is correct
17 Correct 84 ms 1104 KB Output is correct
18 Correct 110 ms 1388 KB Output is correct