oj.uz

답안 #421285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421285 2021-06-09T00:54:41 Z zaneyu Monster Game (JOI21_monster) C++17
68 / 100
 191 ms 1676 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;
int cnt=0;
bool cmp(int a,int b){
    if(mp.count({a,b})) return mp[{a,b}];
    ++cnt;
    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);
    assert(cnt<=9000);
    //REP(i,n) cout<<arr[i]<<' ';
    vector<int> ans(n);
    vector<int> v;
    REP1(i,3*n/4){
        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[0],arr[i])) break;
                    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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Runtime error 1 ms 328 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Runtime error 1 ms 328 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
68.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 1464 KB Output is correct
2 Partially correct 122 ms 1632 KB Partially correct
3 Partially correct 135 ms 1532 KB Partially correct
4 Partially correct 153 ms 1660 KB Partially correct
5 Partially correct 126 ms 1628 KB Partially correct
6 Correct 72 ms 1336 KB Output is correct
7 Correct 103 ms 1268 KB Output is correct
8 Correct 120 ms 1460 KB Output is correct
9 Partially correct 115 ms 1592 KB Partially correct
10 Partially correct 191 ms 1676 KB Partially correct
11 Partially correct 132 ms 1604 KB Partially correct
12 Partially correct 142 ms 1520 KB Partially correct
13 Correct 96 ms 1344 KB Output is correct
14 Correct 77 ms 1472 KB Output is correct
15 Correct 85 ms 1224 KB Output is correct
16 Correct 72 ms 1032 KB Output is correct
17 Correct 96 ms 1188 KB Output is correct
18 Correct 122 ms 1344 KB Output is correct