Submission #172797

#	Time	Username	Problem	Language	Result	Execution time	Memory
172797		mhy908	Memory 2 (JOI16_memory2)	C++14	0 / 100	2 ms	376 KiB

memory2

#include "Memory2_lib.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int arr[110][3];
int l[110], r[110];
pii ans[110];
int rans[110];
set<pii> pq;
vector<pii> v[110];
void ch(int num){
    if(arr[num][1]==arr[num][2]){
        //printf("pushed %d at %d\n", arr[num][1], num);
        if(pq.find(mp(v[arr[num][1]].size(), arr[num][1]))!=pq.end())
            pq.erase(mp(v[arr[num][1]].size(), arr[num][1]));
        int pl=0;
        v[arr[num][1]].pb(mp(arr[num][1], num));
        if(v[arr[num][1]].size()==2){
            if(r[v[arr[num][1]][0].S]==v[arr[num][1]][1].S)pl=1000;
            if(r[v[arr[num][1]][1].S]==v[arr[num][1]][0].S)pl=1000;
        }
        pq.insert(mp(v[arr[num][1]].size()+pl, arr[num][1]));
    }
}
void f(int NUM){
    if(!NUM)return;
    auto it=pq.end();
    it--;
    int temp=it->S;
    pq.erase(it);
    vector<pii> t=v[temp];
    sort(all(t));
    if(NUM==1){
        ans[t[0].F]=mp(t[0].S, t[1].S);
        return;
    }
    else if(NUM==2&&t.size()==4){
        int tt=Flip(t[0].S, t[2].S);
        ans[tt]=mp(t[0].S, t[2].S);
        tt=Flip(t[1].S, t[3].S);
        ans[tt]=mp(t[1].S, t[3].S);
        return;
    }
    else if(t.size()==2&&r[t[0].S]!=t[1].S&&r[t[1].S]!=t[0].S){
        ans[t[0].F]=mp(t[0].S, t[1].S);
        l[r[t[0].S]]=l[t[0].S];
        r[l[t[0].S]]=r[t[0].S];
        l[r[t[1].S]]=l[t[1].S];
        r[l[t[1].S]]=r[t[1].S];
        int tt=Flip(l[t[0].S], r[t[0].S]);
        arr[l[t[0].S]][1]=tt;
        arr[r[t[0].S]][2]=tt;
        tt=Flip(l[t[1].S], r[t[1].S]);
        arr[l[t[1].S]][1]=tt;
        arr[r[t[1].S]][2]=tt;
        ch(l[t[0].S]);
        ch(r[t[0].S]);
        ch(l[t[1].S]);
        ch(r[t[1].S]);
        l[t[0].S]=r[t[0].S]=l[t[1].S]=r[t[1].S]=-1;
    }
    else if(t.size()==3){
        int num=0, now=t[0].S;
        for(; num<=3; num++){
            if(now!=t[num].S)break;
            now=r[now];
        }
        if(num==2){
            swap(t[0], t[1]);
            swap(t[1], t[2]);
        }
        if(num==3){
            swap(t[1], t[2]);
        }
        ans[t[0].F]=mp(t[0].S, t[1].S);
        l[r[t[0].S]]=l[t[0].S];
        r[l[t[0].S]]=r[t[0].S];
        l[r[t[1].S]]=l[t[1].S];
        r[l[t[1].S]]=r[t[1].S];
        int tt=Flip(l[t[0].S], r[t[0].S]);
        arr[l[t[0].S]][1]=tt;
        arr[r[t[0].S]][2]=tt;
        tt=Flip(l[t[1].S], r[t[1].S]);
        arr[l[t[1].S]][1]=tt;
        arr[r[t[1].S]][2]=tt;
        vector<int> need;
        need.pb(r[t[0].S]);
        need.pb(l[t[0].S]);
        need.pb(r[t[1].S]);
        need.pb(l[t[1].S]);
        sort(all(need));
        need.erase(unique(all(need)), need.end());
        for(auto p:need)ch(p);
        l[t[0].S]=r[t[0].S]=l[t[1].S]=r[t[1].S]=-1;
    }
    else if(t.size()==2){
        if(r[t[1].S]==t[0].S)swap(t[0], t[1]);
        ans[t[0].F]=mp(t[0].S, t[1].S);
        l[r[t[1].S]]=l[t[0].S];
        r[l[t[0].S]]=r[t[1].S];
        int tt=Flip(l[t[0].S], r[t[1].S]);
        arr[l[t[0].S]][1]=tt;
        arr[r[t[1].S]][2]=tt;
        ch(l[t[0].S]);
        ch(r[t[1].S]);
        l[t[0].S]=r[t[0].S]=l[t[1].S]=r[t[1].S]=-1;
    }
    f(NUM-1);
}
void Solve(int T, int n){
    n*=2;
    for(int i=0; i<n; i++){
        r[i]=(i+1)%n;
        l[(i+1)%n]=i;
    }
	for(int i=0; i<n; i++){
        int t1=Flip(i, (i+1)%n);
        arr[i][1]=t1;
        arr[(i+1)%n][2]=t1;
	}
	for(int i=0; i<n; i++){
        ch(i);
	}
	f(n/2);
	for(int i=0; i<n/2; i++){
        rans[ans[i].F]=i;
        rans[ans[i].S]=i;
	}
	/*for(int i=0; i<n; i++){
        printf("%d ", rans[i]);
	}
	puts("");*/
	for(int i=0; i<n/2; i++){
        Answer(ans[i].F, ans[i].S, i);
	}
}
/*
3 5 100
1 2 3 4 5
4 0 2 1 1 4 3 3 2 0
*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 50
• Subtask 3: 0 / 40