| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 511752 |
2022-01-16T04:17:32 Z |
79brue |
None (JOI16_memory2) |
C++14 |
|
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 |
