QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #391623 | #3784. 一行盒子 | 秦始皇派蒙恬还原神舟十二 (Jiancong Wen, Chu Jin, Zekai Zhang) | 100 ✓ | 46ms | 5268kb | C++17 | 6.0kb | 2024-04-16 17:39:39 | 2024-04-16 17:39:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define int long long
const int N = 1e5 + 20;
int n, m, f[N], ff[N];
void solve()
{
int flag = 1,st = 1;
for(int i = 0; i<= n + 5; i++)
{
f[i] = i - 1;
ff[i] = i + 1;
}
ff[0] = 1;
while(m--)
{
int op,x,y;
cin >> op ;
if(op != 4) cin >> x >> y;
if(flag == 1)
{
if(op == 3)
{
if(f[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[xl] = y;
f[yr] = x;
f[x] = y;
ff[x] = yr;
f[y] = xl;
ff[y] = x;
continue;
}
else if(ff[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[yl] = x;
f[xr] = y;
f[x] = yl;
ff[x] = y;
f[y] = x;
ff[y] = xr;
continue;
}
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[xl] = y;
f[xr] = y;
ff[yl] = x;
f[yr] = x;
f[x] = yl,ff[x] = yr;
f[y] = xl,ff[y] = xr;
}
else if(op == 1)
{
if(ff[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[yl] = x;
f[xr] = y;
f[x] = yl;
ff[x] = y;
f[y] = x;
ff[y] = xr;
continue;
}
int xl = f[x];
int xr = ff[x];
int yl = f[y];
if(yl == x) continue;
ff[xl] = xr;
f[xr] = xl;
ff[yl] = x;
f[y] = x;
f[x] = yl,ff[x] = y;
}
else if(op == 2)
{
if(f[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[xl] = y;
f[yr] = x;
f[x] = y;
ff[x] = yr;
f[y] = xl;
ff[y] = x;
continue;
}
int xl = f[x];
int xr = ff[x];
int yr = ff[y];
if(yr == x) continue;
ff[xl] = xr;
f[xr] = xl;
ff[y] = x;
f[yr] = x;
f[x] = y,ff[x] = yr;
}
else if(op == 4)
{
flag = -flag;
}
}
else
{
if(op == 3)
{
if(f[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[xl] = y;
f[yr] = x;
f[x] = y;
ff[x] = yr;
f[y] = xl;
ff[y] = x;
continue;
}
else if(ff[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[yl] = x;
f[xr] = y;
f[x] = yl;
ff[x] = y;
f[y] = x;
ff[y] = xr;
continue;
}
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[xl] = y;
f[xr] = y;
ff[yl] = x;
f[yr] = x;
f[x] = yl,ff[x] = yr;
f[y] = xl,ff[y] = xr;
}
else if(op == 2)
{
if(ff[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[yl] = x;
f[xr] = y;
f[x] = yl;
ff[x] = y;
f[y] = x;
ff[y] = xr;
continue;
}
int xl = f[x];
int xr = ff[x];
int yl = f[y];
if(yl == x) continue;
ff[xl] = xr;
f[xr] = xl;
ff[yl] = x;
f[y] = x;
f[x] = yl,ff[x] = y;
}
else if(op == 1)
{
if(f[y] == x)
{
int xl = f[x];
int xr = ff[x];
int yl = f[y];
int yr = ff[y];
ff[xl] = y;
f[yr] = x;
f[x] = y;
ff[x] = yr;
f[y] = xl;
ff[y] = x;
continue;
}
int xl = f[x];
int xr = ff[x];
int yr = ff[y];
if(yr == x) continue;
ff[xl] = xr;
f[xr] = xl;
ff[y] = x;
f[yr] = x;
f[x] = y,ff[x] = yr;
}
else if(op == 4)
{
flag = -flag;
}
}
}
for(int i = 1; i <= n; i++)
{
if(flag == 1)
{
if(f[i] == 0)
{
st = i;
break;
}
}
else
{
if(ff[i] == n + 1)
{
st = i ;
break;
}
}
}
int ans = 0;
if(flag == 1)
{
for(int i = st,j = 1; j <= n && i >= 1 && i <= n; j ++, i = ff[i] )
{
if(j & 1)
{
ans += i;
}
}
}
else
{
for(int i = st,j = 1; j <= n && i >= 1 && i <= n; j ++ ,i = f[i])
{
if(j & 1)
{
ans += i;
}
}
}
cout << ans << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while(cin >> n >> m)
{
cout << "Case " << T++ << ": ";
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 46ms
memory: 5268kb
input:
2 1 3 1 2 10 10 2 3 6 2 10 2 4 3 4 2 2 10 8 1 5 7 3 6 9 3 2 4 4 1 2 3 100 1000 2 12 76 1 6 97 3 80 78 3 23 75 3 88 78 3 48 11 4 4 2 22 89 4 2 60 11 1 92 11 2 39 49 4 4 1 22 47 1 48 14 1 60 58 1 37 40 3 4 36 4 2 39 55 1 62 71 4 1 91 4 4 1 50 49 3 42 29 2 73 47 1 28 93 2 22 97 2 50 32 1 17 38 4 2 8 22...
output:
Case 1: 2 Case 2: 26 Case 3: 2622 Case 4: 10213 Case 5: 2983 Case 6: 2499756727 Case 7: 252019 Case 8: 25055565 Case 9: 2500000000 Case 10: 2500000000
result:
ok 10 lines