| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 172797 |
2020-01-02T16:14:52 Z |
mhy908 |
None (JOI16_memory2) |
C++14 |
|
2 ms |
376 KB |
#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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Wrong Answer[1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
256 KB |
Wrong Answer[1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Wrong Answer[1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
