Submission #511752

#	Time	Username	Problem	Language	Result	Execution time	Memory
511752		79brue	Memory 2 (JOI16_memory2)	C++14	100 / 100	1 ms	332 KiB

memory2

#include "Memory2_lib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
vector<int> ans[102];
vector<int> unknown;

void Solve(int T, int N){
	n = N;
	for(int i=0; i<n+n; i++) unknown.push_back(i);
	while((int)unknown.size() >= 3){
        vector<int> vec, qv;
        for(int i=0; i<3; i++) vec.push_back(unknown[i]);
        for(int i=0; i<3; i++) qv.push_back(Flip(unknown[i], unknown[(i+1)%3]));
        if(*min_element(qv.begin(), qv.end()) != *max_element(qv.begin(), qv.end())){
            int big = (qv[0] == qv[1] ? qv[2] : qv[0] == qv[2] ? qv[1] : qv[0]);
            int small = (qv[0] + qv[1] + qv[2] - big) / 2;

            int i = find(qv.begin(), qv.end(), big) - qv.begin();
            i = (i+2)%3;
            ans[small].push_back(vec[i]);
            unknown.erase(find(unknown.begin(), unknown.end(), vec[i]));
            continue;
        }

        /// 세 리턴 값이 모두 같게 나온 경우
        int small = qv[0];
        while((int)unknown.size() >= 4){
            int idx = unknown.back();
            vector<pair<int, int> > qv2;
            for(int i=0; i<3; i++) qv2.push_back(make_pair(Flip(idx, unknown[i]), i));
            sort(qv2.begin(), qv2.end());
            if(qv2[0].first == qv2[2].first){ /// 세 값이 모두 같은 경우
                ans[qv2[0].first].push_back(idx);
                unknown.pop_back();
                continue;
            }
            if(qv2[0].first == qv2[1].first){ /// 앞 두 값이 같은 경우
                ans[small].push_back(unknown[qv2[0].second]);
                ans[small].push_back(unknown[qv2[1].second]);
                int X = unknown[qv2[0].second];
                int Y = unknown[qv2[1].second];
                unknown.erase(find(unknown.begin(), unknown.end(), X));
                unknown.erase(find(unknown.begin(), unknown.end(), Y));
                break;
            }
            if(qv2[1].first == qv2[2].first){ /// 앞 두 값이 같은 경우
                ans[small].push_back(unknown[qv2[2].second]);
                ans[small].push_back(unknown[qv2[1].second]);
                int X = unknown[qv2[2].second];
                int Y = unknown[qv2[1].second];
                unknown.erase(find(unknown.begin(), unknown.end(), X));
                unknown.erase(find(unknown.begin(), unknown.end(), Y));
                break;
            }
            exit(1);
        }
        if((int)unknown.size() == 3) break;
	}

	vector<int> remain;
	for(int i=0; i<n; i++) for(int j=0; j<2-(int)ans[i].size(); j++) remain.push_back(i);

	if((int)unknown.size() == 1){
        ans[remain[0]].push_back(unknown[0]);
	}
	else if((int)unknown.size() == 2){
        if(remain[0] == remain[1]){
            ans[remain[0]].push_back(unknown[0]);
            ans[remain[0]].push_back(unknown[1]);
        }
        else{
            int small = Flip(ans[remain[0]][0], ans[remain[1]][0]);
            int big = remain[0] + remain[1] - small;
            ans[Flip(ans[big][0], unknown[0])].push_back(unknown[0]);
            ans[Flip(ans[big][0], unknown[1])].push_back(unknown[1]);
        }
	}
	else if((int)unknown.size() == 3){
        if(remain[0] == remain[1] || remain[1] == remain[2]){ /// A A B
            if(remain[1] == remain[2]) swap(remain[0], remain[2]);

            vector<int> tVec;
            for(int i=0; i<3; i++) tVec.push_back(Flip(ans[remain[2]][0], unknown[i]));
            if(*min_element(tVec.begin(), tVec.end()) != *max_element(tVec.begin(), tVec.end())){
                for(int i=0; i<3; i++) ans[tVec[i]].push_back(unknown[i]);
            }
            else{ /// A B B
                int small = tVec[0];
                vector<int> tVec2;
                for(int i=0; i<3; i++) tVec2.push_back(Flip(unknown[(i+2)%3], unknown[(i+1)%3]));
                int big = *max_element(tVec2.begin(), tVec2.end());
                for(int i=0; i<3; i++){
                    if(tVec2[i] == big){
                        ans[small].push_back(unknown[i]);
                        ans[big].push_back(unknown[(i+1)%3]);
                        ans[big].push_back(unknown[(i+2)%3]);
                    }
                }
            }
        }
        else{ /// A B C
            vector<int> tVec;
            for(int i=0; i<3; i++) for(int j=i+1; j<3; j++) tVec.push_back(Flip(ans[remain[i]][0], ans[remain[j]][0]));
            sort(tVec.begin(), tVec.end());
            tVec.erase(unique(tVec.begin(), tVec.end()), tVec.end());
            int big = remain[0] + remain[1] + remain[2] - tVec[0] - tVec[1];

            for(int i=0; i<3; i++) ans[Flip(ans[big][0], unknown[i])].push_back(unknown[i]);
        }
	}

	for(int i=0; i<n; i++){
        Answer(ans[i][0], ans[i][1], i);
	}
}

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