Submission #511752

# Submission time Handle Problem Language Result Execution time Memory
511752 2022-01-16T04:17:32 Z 79brue None (JOI16_memory2) C++14
100 / 100
1 ms 332 KB
#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);
	}
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 272 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 300 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 292 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 204 KB Output is correct