Submission #172773

#	Time	Username	Problem	Language	Result	Execution time	Memory
172773		mhy908	Memory 2 (JOI16_memory2)	C++14	0 / 100	4 ms	504 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];
priority_queue<pii, vector<pii>, greater<pii> > pq;
void ch(int num){
    if(arr[num][1]==arr[num][2]){
        //printf("pushed %d at %d\n", arr[num][1], num);
        pq.push(mp(arr[num][1], num));
    }
}
void f(int NUM){
    if(!NUM)return;
    int temp=pq.top().F;
    vector<pii> t;
    while(pq.size()){
        if(pq.top().F==temp){
            t.pb(pq.top());
            pq.pop();
        }
        else break;
    }
    if(NUM==1){
        ans[t[0].F]=mp(t[0].S, t[1].S);
        return;
    }
    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;
    }
    if(t.size()==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;
        ch(l[t[0].S]);
        ch(r[t[0].S]);
        ch(l[t[1].S]);
        ch(r[t[1].S]);
    }
    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]);
        }
        else{
            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;
        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[0].S]=-1;
    }
    if(t.size()==4){
        int num=0, now=t[0].S;
        for(; num<=4; num++){
            if(now!=t[num].S)break;
            now=r[now];
        }
        if(num==1){
            swap(t[0], t[2]);
            swap(t[1], t[3]);
        }
        if(num==2){
            swap(t[1], t[3]);
        }
        if(num==4){
            swap(t[0], t[1]);
            swap(t[1], t[2]);
        }
        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]);
    }
    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++){
        Answer(ans[i].F, ans[i].S, i);
	}
}
/*
3 4 24
1 2 3 4
1 0 2 3 1 2 3 0
*/

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